03、无重复字符的最长子串
字符串里的字符重复后,不必把整个搜索过程推倒重来。只要移动左边界,把导致重复的旧字符移出窗口,就能继续向右处理。
问题与目标
LeetCode 3:无重复字符的最长子串要求返回不含重复字符的最长连续子串长度。
abcabcbb → 3,对应abc
bbbbb → 1,对应b
abba → 2,对应ab或ba
“子串”必须连续,不是可以跳着选择字符的“子序列”。空字符串返回 0。
维护窗口,而不是反复枚举起点
让 [left,right] 表示当前无重复窗口。记录每个字符上一次出现的位置 last;读到新字符时,如果它上次的位置仍在当前窗口内,就将 left 推进到那个位置之后。
如果旧位置已经在窗口左侧,就不移动 left。等价地,可以用 left = max(left, last + 1)。左边界只能向右,不能回退。

为什么 abba 是必要测试
读到第二个 b 时,旧 b 在下标 1,因此 left 变为 2。继续读到下标 3 的 a,旧 a 在下标 0,早已不在当前窗口里;left 应保持 2,窗口为 ba。
如果无条件把 left 写成 last[a] + 1 = 1,窗口就会回退成含两个 b 的 bba,错误地得到长度 3。这是只测 abcabcbb 容易漏掉的问题。
C++17 实现
#include <algorithm>
#include <array>
#include <string>
class Solution {
public:
int lengthOfLongestSubstring(const std::string& text) {
std::array<int, 256> last;
last.fill(-1);
int left = 0;
int answer = 0;
for (int right = 0; right < static_cast<int>(text.size()); ++right) {
const auto value = static_cast<unsigned char>(text[right]);
if (last[value] >= left) left = last[value] + 1;
last[value] = right;
answer = std::max(answer, right - left + 1);
}
return answer;
}
};
复杂度与字符边界
每个字节扫描一次,固定表访问 O(1),总时间 O(n),辅助空间 O(256),在固定字节字符集下可称 O(1)。
代码针对本题的英文字母、数字、符号和空格,按常见 8 位字节实现字符表。先转换为 unsigned char 是为了避免负的 char 值被当成数组下标。输入长度沿用题目范围,可用 int 表示位置。
UTF-8 中文字符可能占多个字节,不能把这个版本直接称为“按 Unicode 字符计算长度”。真实多语言产品需要先明确按码点还是用户感知字符划分,再调整窗口数据。
常见误区
窗口长度包含两个端点,要加 1;先更新 last 再判断,会把当前字符误当旧重复;无条件回退 left 会破坏窗口不变量。面试时把这三个操作的顺序讲清,比只说“使用滑动窗口”更有说服力。
