LeetCode 3. 无重复字符的最长子串 - HashSet 与 HashMap 滑动窗口解法

题目回顾

给定一个字符串 s，请你找出其中不含有重复字符的 最长子串 的长度。

示例

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

输入：""
输出：0

核心思路：滑动窗口

这道题的核心就是滑动窗口的思想：维护一个窗口 [left, right]，保证这个窗口里的字符都是不重复的。不断移动右指针扩大窗口，遇到重复字符的时候，就移动左指针缩小窗口，直到窗口里没有重复字符，全程记录最大的窗口长度。

相比暴力枚举所有子串的 O(n²) 解法，滑动窗口可以把时间复杂度降到 O(n)，每个字符最多被访问两次，效率高了很多。

解法一：HashSet 实现滑动窗口

这是滑动窗口的基础写法，比较直观，容易理解，适合新手入门。

步骤拆解

1. 初始化指针：左指针 left 和右指针 right 都从 0 开始，temp 记录当前窗口的长度，res 记录最大的长度。
2. 初始化 HashSet：注意 Set 的类型是 Character 不是 char，因为 Java 的泛型不能用基本类型，用来存当前窗口里的字符。
3. 循环条件：只要右指针小于字符串的长度，就继续处理。
4. 拿到当前右指针指向的字符 cur：
   • 如果 Set 里已经包含了 cur，说明窗口里有重复了，我们要移动左指针缩小窗口：把左指针指向的字符从 Set 里删掉，左指针右移一位，当前窗口长度 temp 减一。
   • 如果 Set 里不包含 cur，说明可以扩大窗口：把 cur 加入 Set，右指针右移一位，当前窗口长度 temp 加一，然后更新 res 为 max(res, temp)，记录最大的长度。
5. 最后返回 res 就可以了。

代码实现

class Solution {
       {
           , right = , temp = , res = ;
        HashSet<Character> set =  <>();
         (right < s.length()) {
               s.charAt(right);
             (set.contains(cur)) {
                set.remove(s.charAt(left));
                left++;
                temp--;
            }  {
                set.add(cur);
                right++;
                temp++;
                res = Math.max(temp, res);
            }
        }
         res;
    }
}