LeetCode: 3. 无重复字符的最长子串

1. 核心思路

1. 滑动窗口

维持一个滑动的窗口，里面的字符都是唯一的，如果滑动窗口的长度大于以前的最大子串，则更新最大长度

2. 为什么要用滑动窗口

显然，易证；由题意可知；略；懂的都懂，不懂的也解释不了

我们不妨以示例一中的字符串 abcabcbb 为例，找出 从每一个字符开始的，不包含重复字符的最长子串，那么其中最长的那个字符串即为答案。对于示例一中的字符串，我们列举出这些结果，其中括号中表示选中的字符以及最长的字符串：

以(a)bcabcbb 开始的最长字符串为 (abc)abcbb；
以a(b)cabcbb 开始的最长字符串为 a(bca)bcbb；
以 ab(c)abcbb 开始的最长字符串为 ab(cab)cbb；
以 abc(a)bcbb 开始的最长字符串为 abc(abc)bb；
以 abca(b)cbb 开始的最长字符串为 abca(bc)bb；
以 abcab(c)bb 开始的最长字符串为 abcab(cb)b；
以 abcabc(b)b 开始的最长字符串为 abcabc(b)b；
以 abcabcb(b) 开始的最长字符串为 abcabcb(b)。

如果我们依次递增地枚举子串的起始位置，那么子串的结束位置也是递增的！这里的原因在于，假设我们选择字符串中的第 k个字符作为起始位置，并且得到了不包含重复字符的最长子串的结束位置为 r_k。那么当我们选择第 k+1个字符作为起始位置时，首先从 k+1到 r_k的字符显然是不重复的，并且由于少了原本的第 k个字符，我们可以尝试继续增大 r_k，直到右侧出现了重复字符为止。
(节选自：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/wu-zhong-fu-zi-fu-de-zui-chang-zi-chuan-by-leetc-2/)

2. 具体步骤

• 由上述分析可知，我们要不断枚举子串的起始位置，然后得出从哪个位置开始的无重复子串的长度最长
• 显然，并不是开始位置越小，无重复子串越长，只是开始位置越小，可能的 无重复子串越长！
• 结束位置呢？从字符串第一个位置开始，不断向后遍历，直到有重复的字符为止
• 用一个集合（set）保存此次遍历的字符，因为集合特性-无重复元素，集合里的元素就是当前的无重复子串
• 被结束位置指向的字符放入集合中
• 结束的一次遍历结束时，判断一下是否超过以前的最大长度，超过了就更新最大长度
• 如果出现了重复元素呢？怎么进行下一次遍历？如何定位到发生重复的元素？
• 答案很简单，在集合中删除开始位置指向的字符，然后开始位置向前移动一步，开始下次遍历。
• 就这？九折？为什么删除开始位置指向的字符串就完了啊？重复的元素又不一定是它，删除后，下次遍历一样有重复元素啊
• 确实。但那又有什么影响呢？下次遍历有重复，那么开始位置继续向前，直到没有为止
• 这就是一般人的思维和计算机思维的区别
• 在 滑动窗口 的分析中可知结束位置不变的话，最大长度是不会变的，只要有重复元素，结束位置就不会变
• 首先你要知道人是如何解决问题的，然后想到怎么教计算机用类似的方法解决
• 当然，大部分人想到的都是 暴力解法 ，暴力解法永远是最后一个选项，如果你把自己当做一个合格的猿类

3. 实现代码

    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        int n = s.length();
        int start = 0, end = -1, max =0;
        for(;start<n;start++){
            // end + 1表示下一个要添加的字符的下标
            // 初始值为-1，因为最开始要添加的字符下标为0，即下一个位置为0
            while (end+1 < n && !set.contains(s.charAt(end+1))){
                set.add(s.charAt(end +1));
                end ++;
            }
            // 遍历完一个起始位置，多个结束位置后，判断是否超过以前的最大值
            max = Math.max(max, end-start +1);
            // 以这个字符开头的所有子串遍历完了，删除后遍历下一个
            set.remove(s.charAt(start));
        }
        return max;
    }

def lengthOfLongestSubstring(self, s: str) -> int:
    c_set = set()
    start, end, ans, n = 0, -1, 0,len(s)
    for start in range(0, n):
        while end+1 < n and s[end+1] not in c_set:
            c_set.add(s[end+1])
            end += 1
        ans = max(ans, end-start+1)
        c_set.remove(s[start])

    return ans

人生苦短，我用Py

4. 最后总结

这是我的第一篇LeetCode题解，为什么要写这东西？加深自己印象，帮助他人解题

这题 的突破口是 要想到 从每一个字符开始的，不包含重复字符的最长子串，然后想到滑动窗口

计算机专业的对滑动窗口应该很熟悉了，那么滑动窗口在计算机相关领域的哪些地方有实际运用呢？

没经过任何训练，没得到任何提示就能想到这解法的确实厉害。