欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode3---无重复字符的最长子串

程序员文章站 2024-02-25 15:51:21
...

给定一个字符串,找出不含有重复字符的 最长子串 的长度。

示例:

给定 “abcabcbb” ,没有重复字符的最长子串是 “abc” ,那么长度就是3。

给定 “bbbbb” ,最长的子串就是 “b” ,长度是1。

给定 “pwwkew” ,最长子串是 “wke” ,长度是3。请注意答案必须是一个子串,”pwke” 是 子序列 而不是子串。

首先讲下最容易想到效率也是最低的一个方法。

分析:我们要找最长子串长度,可以在查找过程中维持一个窗口,开始前后端点都在字符串起点,遍历数组,如果新字符不存在窗口内,后端点后移,如果新字符存在窗口内,计算当前窗口长度,取最大值,同时窗口前端点移动到出现重复字符的位置,后端点后移。
这样复杂度会接近n^2。

代码:

public int lengthOfLongestSubstring(String s) {
        if (s.trim().equals("")){
            return 0;
        }
        int answer = 1;
        int left = 0;
        int current = 0;
        for (int i=0; i<s.length(); i++){
            current = i;
            int temp;
            if ((temp = isExist(s, left, current)) >= 0){
                answer = Math.max(answer, current-left);
                left = temp+1;
            }
        }
        answer = Math.max(answer, current-left+1);
        return answer;
    }

    private int isExist(String s, int left, int right){
        for (int i=left; i<right; ++i){
            if (s.charAt(i) == s.charAt(right)){
                return i;
            }
        }
        return -1;
    }

这个题目操作有两步,第一步在原数组移动,第二步在当前维持的窗口中查找新字符是否已存在。第二部既然是查找,那么我们是不是可以优化呢。当然是可以的,查找有二分查找,hash查找等,这题我们采用hash查找的思路来,这个题目只有普通的ascii码字符,那么我们就有两种方式来优化这个查找。
1、开一个256长度的int数组prevChar,prevChar[i]表示ascii码为i的字符上次出现的位置下标,那么当前字符的上次出现的下标如果小于窗口起始下标,那么这个字符在当前窗口就是不存在的,否则就是重复出现的。实现如下,复杂度为O(n):

public int lengthOfLongestSubstring(String s) {
        if (s.trim().equals("")){
            return 0;
        }
        int answer = 1;
        int len = 0;
        int currentStart = 0;
        int[] prevChar = new int[256];
        for (int i=0; i<prevChar.length; ++i){
            prevChar[i] = -1;
        }
        for (int i=0; i<s.length(); ++i){
            if (prevChar[s.charAt(i)] < currentStart){
                len++;
                answer = Math.max(answer, len);
            }else {
                currentStart = prevChar[s.charAt(i)] + 1;
                len = i - currentStart + 1;
            }
            prevChar[s.charAt(i)] = i;
        }
        return answer;
    }

2、使用hashmap来实现查找,思路和上面一模一样,只是将数组存储换为了hashmap存储,这种方式更为通用,但是由于hashmap会有很多装箱操作以及一些内部操作,速度上不如数组存储快。实现如下:

public int lengthOfLongestSubstring_map(String s) {
        if (s.trim().equals("")){
            return 0;
        }
        int answer = 1;
        int len = 0;
        int currentStart = 0;
        HashMap<Character, Integer> charMap = new HashMap<>(64);
        for (int i=0; i<s.length(); ++i){
            if ( !charMap.containsKey(s.charAt(i)) || charMap.get(s.charAt(i)) < currentStart){
                len++;
                answer = Math.max(answer, len);
            }else {
                currentStart = charMap.get(s.charAt(i)) + 1;
                len = i - currentStart + 1;
            }
            charMap.put(s.charAt(i), i);
        }
        return answer;
    }