不重复子字符串

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

示例 1:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串

思考

暴力法

首先把子串找出来，然后判断是否重复。判断是否重复的过程，如果用遍历的方法就有点low了，这是主要是一个快速查找，可以用set，其实和去重差不多。

我的思考

这种题，我一般喜欢看看有没有dp的解法，一般是考虑以每个字符结尾的结果。以abaab为例

• 如果子串以a结尾，长度为1
• 如果字串以b结尾，判断b在之前出现过没，如果没有，判断a出现过没。
• 最后找出最大的长度

参考解法

同学提示了下，他说这个其实可以用滑动窗口，具体过程如下、

• right = 1, left = 0， set维护不重复子串
• left所指向的字符加入set
• right所指向的字符如果在set , 说明重复出现，开始计算长度，并把left++, 暴力解法中right执行需要回退到left + 1处，把set清空进入下一次循环。但是我们可以进行优化，就是left移动前的对应的元素给删除了，right不变。现在想想，这其实是利用了不重复子串的left指针前移一次仍然是不重复的，所以没有必要回退。
• 这里代码有个坑，当循环结束后，还要比较一次set里的长度和当前长度。如‘aq‘

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // fast = 1 slow = 0 
        //1. slow 加到map
        // 2. 观察fast是否可以在map中，如果不再，则fast++,否则slow ++ ，统计长度， slow里面要删除. 滑动窗口

        if (s == null || s.length() == 0) {
            return 0;
        }

        char[] chars = s.toCharArray();
        int left = 0;
        int right = 1;
        int len = s.length();
        int result = 1;
        Set<Character> set = new HashSet<>();
        set.add(chars[left]);


        while(right < len) {
            char curChar = chars[right];
            if (set.contains(curChar)) {
                // 统计长度
                result = Math.max(result, right - left);
                set.remove(chars[left]);
                left++;
            } else {
                set.add(curChar);
                right++;
            }
        }

        result = Math.max(result, set.size());
        return result;
    }
}

不重复子字符串

原文：https://www.cnblogs.com/jielearscoding/p/15027443.html