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

题目链接

无重复字符的最长子串

题目描述

题目解析

问题背景

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

算法核心思想

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

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

代码关键部分解析

1. 哈希表的作用：

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);

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

完整代码

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

1. 滑动窗口：用left和right两个指针表示当前正在处理的子串区间，right主动右移扩展窗口，left被动右移缩小窗口以保证窗口内无重复字符。
2. 哈希表作用：实时记录窗口内每个字符的出现次数，当right指向的字符出现次数超过 1 时，通过移动left并减少对应字符的计数，直到窗口内无重复字符。
3. 时间复杂度：每个字符最多被left和right各访问一次，因此为 O (n)（n 为字符串长度）。

注意事项

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