LeetCode 3：无重复字符的最长子串（滑动窗口解法）

记录一下刷题日常。这道题是非常经典的滑动窗口问题，主要利用双指针维护一个不包含重复字符的“窗口”，配合 HashSet 进行去重。

💡解题思路

1. 定义双指针与集合： 定义 left 和 right 两个指针，初始都指向字符串的开头。再定义一个 HashSet，用来记录当前窗口内出现了哪些字符。

2. 窗口扩张（右指针移动）： 遍历字符串，让 right 指针不断向右移动，每次尝试将 s.charAt(right) 加入窗口。

3. 窗口收缩（左指针移动）： 如果发现当前 right 指针指向的字符已经存在于 HashSet 中，说明出现了重复字符。此时，我们必须让 left 指针不断向右移动，并同步把移出窗口的字符从 HashSet 中删除，直到窗口内不再包含这个重复的字符为止。

4. 更新最大长度： 每次确保窗口内没有重复字符后，计算当前窗口的长度 (right - left + 1)，并与历史最大长度 max 进行比较，保留最大值。

💻代码实现

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 采用滑动窗口区间，定义左右两个指针，记录最大长度
        int left = 0, max = 0;
        // 定义一个 set 存储当前窗口内的子串字符
        Set<Character> set = new HashSet<>();
        
        // 右指针主动向右移动
        for(int right = 0; right < s.length(); right++) {
            // 如果当前右指针指向的元素在 set 中存在，说明重复了
            while(set.contains(s.charAt(right))) {
                // 移除左指针指向的元素，并将左指针右移收缩窗口
                set.remove(s.charAt(left));
                left++;
            }
            // 将当前字符加入 set
            set.add(s.charAt(right));
            // 更新最大长度
            max = Math.max(max, right - left + 1);
        }
        return max;
    }
}

📊复杂度分析

• 时间复杂度：O(N) 其中 N 是字符串的长度。虽然代码里有一个嵌套的 while 循环，但仔细观察会发现，左指针 left 和右指针 right 在整个过程中都只会向右移动，绝不回头。每个字符最多被 right 指针访问一次加入集合，被 left 指针访问一次移出集合。因此总的时间复杂度是线性的。

• 空间复杂度：O(Σ) 其中 Σ 表示字符集的大小（例如字符串只包含 ASCII 字符，那么集合最大也就是 128）。HashSet 中最多存储当前窗口中的字符，空间开销取决于字符集的种类数。

🎯总结

这道题是滑动窗口的绝佳模板题。核心逻辑就是一句：右边界主动扩张找可行解，一旦不满足条件，左边界就开始收缩直到重新满足条件。