[优选算法专题二滑动窗口——无重复字符的最长子串]

题目链接

无重复字符的最长子串

题目描述

题目解析

问题背景

"无重复字符的最长子串" 问题要求在一个字符串中找到最长的不包含重复字符的连续子串，并返回其长度。这是一个经典的字符串处理问题，滑动窗口算法是解决该问题的最优方案。

算法核心思想

该算法采用滑动窗口 (Sliding Window) 结合哈希表 (Hash Table) 的方式：

• 滑动窗口由左右两个指针界定，代表当前正在检查的子串
• 右指针主动扩展窗口，探索新的字符
• 当遇到重复字符时，左指针被动收缩窗口，确保窗口内始终无重复字符
• 哈希表用于记录窗口内每个字符的出现次数，快速判断是否有重复

代码关键部分解析

unordered_map<char, int> ans;

这里的哈希表用于记录当前窗口中每个字符的出现次数，而不是字符的位置，这是一种常见的实现方式。

2.右指针移动：

for (int left = 0, right = 0; right < n; right++) {
char c = s[right];
ans[c]++;
// …
}

右指针每次向右移动一位，将新字符加入窗口并更新其计数。

3.处理重复字符：

while (ans[c] > 1) {
ans[s[left]]–;
left++;
}

当新加入的字符导致重复（计数 > 1）时，通过移动左指针并减少相应字符的计数，直到窗口内不再有重复字符。

4.更新最长长度：

len = max(len, right – left + 1);

每处理一个新字符后，都要检查当前窗口是否是最长的，并更新结果。

完整代码

核心思路：滑动窗口 + 哈希表

注意事项

• 哈希表ans的键是字符，值是该字符在当前窗口中的出现次数，而非索引（与另一种用哈希表存索引的实现方式不同）。
• 循环条件while (ans[c] > 1)确保窗口内始终无重复字符，此时计算窗口长度并更新结果。