最长不重复子串（Longest Substring Without Repeating Characters）
力扣第 3 题。找出一个字符串中，不含重复字符的最长子串的长度。
核心思路：滑动窗口
维护一个窗口 [left, right)，保证窗口内永远没有重复字符。right 不断向右扩张，一旦遇到重复字符，就把 left 向右收缩，直到重复消除。
解法一：哈希集合（直观版）
cpp
int lengthOfLongestSubstring(string s) {
unordered_set<char> window;
int left = 0, ans = 0;
for (int right = 0; right < s.size(); right++) {
// 如果右边新字符已在窗口中，持续收缩左边
while (window.count(s[right])) {
window.erase(s[left]);
left++;
}
window.insert(s[right]);
ans = max(ans, right - left + 1);
}
return ans;
}
- 时间 O(n)，空间 O(∣Σ∣)（字符集大小，最多 128）
right和left合计最多各走 n 步，所以是 O(n) 而非 O(n²)
解法二：哈希表记录下标（最优，一步到位跳跃）⭐
上面的解法在遇到重复时要一步步移动 left。用哈希表记录每个字符上次出现的位置，可以让 left 直接跳过去，省去 while 循环。
cpp
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> last_pos; // 字符 -> 上次出现的下标
int left = 0, ans = 0;
for (int right = 0; right < s.size(); right++) {
char c = s[right];
// 如果 c 之前出现过，且在窗口内（>= left），则直接跳跃
if (last_pos.count(c) && last_pos[c] >= left) {
left = last_pos[c] + 1;
}
last_pos[c] = right;
ans = max(ans, right - left + 1);
}
return ans;
}
关键在 last_pos[c] >= left 这个判断——如果上次出现的位置已经在窗口左边之外，说明它不影响当前窗口，不需要移动 left。
解法三：数组代替哈希表（极致优化）
如果字符集是 ASCII（128个），用数组比 unordered_map 更快，避免哈希计算开销：
cpp
int lengthOfLongestSubstring(string s) {
int last_pos[128];
fill(last_pos, last_pos + 128, -1); // 初始化为 -1 表示未出现
int left = 0, ans = 0;
for (int right = 0; right < s.size(); right++) {
int c = s[right];
if (last_pos[c] >= left) {
left = last_pos[c] + 1;
}
last_pos[c] = right;
ans = max(ans, right - left + 1);
}
return ans;
}
实战中这版最快，常数因子最小。
三种解法对比
| 解法 | 时间 | 空间 | 特点 |
|---|---|---|---|
| 哈希集合 + while | O(n) | O(|Σ|) | 最直观，适合讲思路 |
| 哈希表记录下标 | O(n) | O(|Σ|) | 面试推荐，逻辑最清晰 |
| 数组代替哈希 | O(n) | O(128) | 性能最佳，竞赛常用 |
两道题的共同模式
接雨水和这道题，一个用双指针从两端往中间，一个用滑动窗口从左往右，都是 O(n) 搞定看似需要 O(n²) 的问题。
面试时把”为什么不用暴力”和”窗口收缩的正确性”讲清楚，比直接背代码更能拿到高分。