leetecode 3 最长无重复字符子串

https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

暴力求解会超时。有两种滑动窗口的方法,时间都差不多。

    public int lengthOfLongestSubstring(String s) {
        int i = 0;
        int j = 0;
        int ans = 0;
        Set<Character> win = new HashSet<>();
        int n = s.length();
        while (i < n && j < n) {
            if (win.contains(s.charAt(j))) {
                win.add(s.charAt(j));
                ans = Math.max(ans, j - i);
                j++;
            } else {
                win.remove(s.charAt(i));
                i++;
            }
        }
        return ans;
    }

上面是第一种,思路是做一个滑动窗口,从头滑到尾,统计最长子串。

    public int lengthOfLongestSubstring2(String s) {
        int n = s.length();
        HashMap<Character,Integer> map = new HashMap<>();
        int j=0;
        int ans = 0;
        for(int i=0;i<n;i++){
            if(map.containsKey(s.charAt(i))){
                j = Math.max(map.get(s.charAt(i)),j);
            }
            ans = Math.max(ans,i-j+1);
            map.put(s.charAt(i),i+1);
        }
        return ans;
    }

第二种如上,我们在做滑动窗口的时候,假如我们的窗口为[j,i],然后Si'(索引是map[s[i]]-1)和Si重复,我们把j滑动到i'+1,然后重新计算子串长度。保留最大子串长度。

这个要比找出最长子串简单一点。

题解还给出了一个更快的方法,思路是一样的,但是利用一个长数组代替映射:

public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        int[] index = new int[128]; // current index of character
        // try to extend the range [i, j]
        for (int j = 0, i = 0; j < n; j++) {
            i = Math.max(index[s.charAt(j)], i);
            ans = Math.max(ans, j - i + 1);
            index[s.charAt(j)] = j + 1;
        }
        return ans;
    }

作者:LeetCode
链接:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/wu-zhong-fu-zi-fu-de-zui-chang-zi-chuan-by-leetcod/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
原文地址:https://www.cnblogs.com/superxuezhazha/p/12266632.html