yicong@algo: ~/code/03-sliding-window/0003-longest-substring-without-repeating-characters.cpp

yicong@algo:~/code/03-sliding-window$ cat 0003-longest-substring-without-repeating-characters.cpp

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

中等 滑动窗口 题目 ↗ 源码 ↗

// 思路

滑动窗口不变量:[left, right] 闭区间内字符互不重复。 right 从左到右扫描,每读入一个新字符 s[right]: - 若已存在于窗口(unordered_set 中),说明 left 需要右移收缩窗口, 不断去掉 s[left] 直到 s[left] == s[right](即重复的那个字符被移出), 再把 left+1 跳过它,此时窗口重新满足无重复。 - 若不存在,直接加入窗口,更新 ans = max(ans, right-left+1)。 关键:left 只增不减,每个字符最多被访问两次(一次入窗口,一次出窗口), 故时间复杂度 O(n)。unordered_set 最多存窗口内字符,字符集有限(ASCII 128), 故空间 O(min(n, 字符集)) = O(n) 最坏,但常数很小。

// 时间复杂度

O(n),每个字符最多入、出窗口各一次

// 空间复杂度

O(min(n, 字符集)),unordered_set 最大存一整个窗口的字符

// 易错点

- left 不回退:若用 if 而非 while,left 可能停在重复字符左边; - 空串:right 循环不进入,直接返回 ans=0,正确; - char 有符号(-128~127),直接做数组下标需转 unsigned char; - 答案在插入前更新:对于 "abca",right=3 时 left=1,窗口长 3,正确; 若在 left 收缩完再更新,则 "abca" 在 right=2 时 ans=3 已记录; - 收缩时 s[left] != s[right] 的判断不能省,否则会把非重复字符也漏删。

// 面试口述要点

- 先说暴力 O(n³) 或哈希集合的朴素滑动窗口 O(n²); - 引出优化点:遇到重复时不用逐个删,而是直接把 left 跳到重复字符右侧; - 进一步优化:用数组记录每个字符上次出现的下标,right 扩张时直接 max(left, last+1), 做到真正的 O(n)/O(1)(无需 set,无需 while 收缩循环),面试常见扩展。

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // ================================================================
    // 版本一:unordered_set 滑动窗口(你的写法)
    // right 扩张,发现重复时 while 收缩,代码直观。
    // ================================================================
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> window;
        int ans = 0;
        int left = 0;
        for (int right = 0; right < (int)s.size(); ++right) {
            if (window.count(s[right])) {
                while (s[left] != s[right]) {
                    window.erase(s[left]);
                    ++left;
                }
                ++left; // 跳过重复字符本身
            } else {
                window.insert(s[right]);
                ans = max(ans, right - left + 1);
            }
        }
        return ans;
    }

    // ================================================================
    // 版本二:数组记录上次出现位置,O(n)/O(1),面试更优写法
    // 核心:遇到字符 c,上次出现位置为 last[c]。
    //   left 必须跳到 max(left, last[c]+1),跳过整个旧出现到当前位置之间所有字符。
    //   无需 set,无需 while 收缩,每次 right 只移动一次。
    // ================================================================
    int lengthOfLongestSubstring_v2(string s) {
        vector<int> last(128, -1);
        int left = 0, ans = 0;
        for (int right = 0; right < (int)s.size(); ++right) {
            unsigned char c = s[right];          // 有符号 char 转下标避免越界
            left = max(left, last[c] + 1);       // 跳过 c 上次出现的位置
            last[c] = right;                     // 更新 c 最近出现位置
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};

// 本地测试:输入一行字符串(可含空格);输出最长无重复子串长度
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    if (!getline(cin, s)) return 0;

    cout << Solution().lengthOfLongestSubstring(s) << '\n';
    return 0;
}