LeetCode 3：无重复字符的最长子串（滑动窗口） —— 题解

欢迎阅读一.题目3. 无重复字符的最长子串 - 力扣LeetCode​ 欢迎来到「无重复字符的最长子串」题解之旅本文将带你从“寻找不含重复字符的最长连续片段”这一经典字符串问题出发深入理解滑动窗口双指针的灵活应用并掌握如何通过哈希表或数组模拟高效维护窗口内字符的唯一性。在开始之前建议你先了解题目背景这是 LeetCode 3 题给定字符串s要求找出不含重复字符的最长子串的长度注意是连续子串不是子序列。本质上是动态维护一个窗口保证窗口内所有字符互不相同并在扩展和收缩过程中记录窗口的最大长度。明确学习目标掌握滑动窗口核心操作——右指针持续向右扩展每加入一个新字符就检查是否重复若重复则移动左指针将重复字符及其之前的字符全部移出窗口直至窗口内无重复。理解如何利用哈希表记录字符最新出现位置或数组计数来快速判断重复并熟练实现双指针扫描 更新最大长度的代码逻辑。准备好环境建议在本地 IDE 或 LeetCode 在线编辑器中打开代码边看边运行亲手验证示例如s abcabcbb输出3s pwwkew输出3。本文将从问题转化、滑动窗口策略设计右扩左缩、重复判定与窗口维护到代码实现层层递进。即使你对滑动窗口还不熟悉我们也会从“用一个窗口框住不重复的字符大了就缩小了就扩”这一直觉出发让你轻松抓住核心思想——窗口内字符唯一是约束条件窗口大小是优化目标双指针负责动态调整。现在让我们一起在字符串中滑动窗口找出那个最长的不重复片段吧 二.做题思路一、问题分析前置分析给定一个字符串s要求找出不含重复字符的最长子串的长度。核心观察当窗口内出现重复字符时只需要移动左指针跳过重复字符右指针无需回退。这是滑动窗口的典型应用可在 O(n) 时间内解决。二、算法策略滑动窗口 哈希表使用哈希表数组模拟记录当前窗口内每个字符的出现次数值为 0 或 1因为窗口内不能有重复。右指针right不断向右扩展每加入一个字符就增加其计数。若当前加入的字符出现次数 ≥ 2说明窗口内有重复此时需要移动左指针left将重复字符从窗口中移除计数置 0直到窗口再次无重复。在窗口有效期间不断更新最长无重复子串的长度。示例执行过程s abcabcbb步骤leftright窗口[left, right]操作当前长度最大长度初始0----0100[a]加入a11201[a,b]加入b22302[a,b,c]加入c33403[a,b,c,a]加入a重复left移到 1移除a33513[b,c,a]窗口有效33614[b,c,a,b]加入b重复left移到 2移除b33724[c,a,b]窗口有效33825[c,a,b,c]加入c重复left移到 3移除c33935[a,b,c]窗口有效331036[a,b,c,b]加入b重复left移到 4移除a331146[b,c,b]加入b仍重复left移到 5移除b231256[c,b]窗口有效231357越界结束--返回 3最终结果为 3对应子串abc、bca或cab。三、正确性说明简单版本滑动窗口维护了一个无重复字符的窗口。每次右指针扩展时若新字符导致重复则移动左指针直到重复消失。因为右指针从不回退每个字符最多被加入和移除窗口各一次所以能遍历所有可能的无重复子串。在窗口有效的每个时刻当前窗口都是以right为右端点的最长无重复子串因此更新最大长度即可得到全局最优解。四、实现细节边界防护使用int hash[128] {0}记录 ASCII 字符出现次数0 或 1。外层for循环中right的更新在循环体内手动控制需注意边界。当hash[s[right]] 1时即新字符已存在进入while循环hash[s[left]] 0移出窗口left继续检查直到窗口内无重复。每次窗口有效时更新len max(len, right - left 1)。注意空字符串处理若n 0直接返回 0。时间复杂度 O(n)空间复杂度 O(1)哈希表大小固定为 128。五、返回值目标映射返回len即最长不含重复字符的子串长度。三.代码#include iostream #include string #include algorithm using namespace std; class Solution { public: int lengthOfLongestSubstring(string s) { // 算法思路滑动窗口 哈希表数组模拟 // 使用 hash 数组记录当前窗口内每个字符出现的次数0或1因为窗口内不能有重复字符 // 右指针 right 不断向右扩展窗口每加入一个字符就增加其计数 // 如果某个字符计数 2说明窗口内出现重复此时移动左指针 left将重复字符从窗口中移除。 // 在窗口有效无重复期间不断更新最长无重复子串的长度。 int hash[128] {0}; // 哈希表用于记录 ASCII 字符在当前窗口中的出现次数值 0 或 1 int n s.size(); int len 0; // 记录当前找到的最长无重复子串长度 // 双指针left 和 right 定义当前窗口 [left, right] // 注意外层 for 循环中 left 和 right 的更新逻辑略复杂但本质仍是滑动窗口 for (int left 0, right 0; right n; ) { // 入窗口将 s[right] 加入窗口计数加1 hash[s[right]]; // 当窗口内没有重复字符时即当前新加入的字符出现次数小于2持续扩展右指针 while (right n hash[s[right]] 2) { // 更新最长无重复子串长度当前窗口长度为 right - left 1 len max(len, right - left 1); // 右指针右移继续扩展窗口 right; // 注意这里再次执行入窗口操作将新字符加入窗口 // 第一次入窗口在循环开始处但 right 移动后需要对新位置进行计数 // 这种写法略显冗余但保证了逻辑完整性 if (right n) { hash[s[right]]; } } // 如果因为 right 越界或出现重复字符而退出 while 循环 // 则说明当前窗口无法继续扩展或已到末尾。 // 此时需要将左指针指向的字符移出窗口将计数置0 // 然后左指针右移尝试缩小窗口以消除重复。 hash[s[left]] 0; // 将 left 指向的字符从窗口中移除计数重置为0 left; // 左指针右移 } // 返回最长无重复子串的长度 return len; } }; int main() { // 测试用例字符串 abcabcbb最长无重复子串是 abc长度为 3 string s abcabcbb; Solution sol; int result sol.lengthOfLongestSubstring(s); cout result endl; // 输出 3 return 0; }四、易错点分析难点一len的更新时机与窗口有效性的关系while (right n hash[s[right]] 2) { len max(len, right - left 1); right; // ... }难点只有窗口内无重复字符时即hash[s[right]] 2才更新len。一旦出现重复循环终止不会更新长度因为此时的窗口是无效的。这要求必须理解len只在窗口“干净”的时候被记录而left的移动则是为了重新使窗口变干净。因此更新长度和移动左指针是两个独立阶段顺序不能颠倒。五、流程图 闭幕 恭喜你完成了「无重复字符的最长子串」问题的学习为了巩固知识并进一步拓展建议你动手实践在 LeetCode 上提交代码尝试不同的测试用例。深入思考本题使用滑动窗口维护一个无重复字符的区间右指针不断扩展当出现重复字符时移动左指针。请问为什么滑动窗口能保证找到最长无重复子串其核心逻辑是什么代码中使用了hash[128]数组来记录字符出现次数。为什么数组大小是 128 而不是 256如果字符串包含中文或其他 Unicode 字符这种方式还适用吗当发现重复字符时hash[s[right]] 2代码将hash[s[left]] 0并left直接清空了左指针指向的字符计数。如果窗口内该字符出现了多次这样的清空方式是否会导致计数错误请结合具体例子说明。代码中的while循环在right未越界且hash[s[right]] 2时不断扩展这种写法与常见的for循环滑动窗口有何异同哪种更易理解本题时间复杂度为O(n)因为每个字符最多被左右指针各访问一次。如果字符串长度n 10^5这个算法是否高效空间复杂度如何延伸挑战如果要求返回最长无重复子串本身而不是长度代码应做哪些调整如果字符集非常大如 Unicode 全部字符不能使用固定数组模拟哈希表你会改用哪种数据结构请说明修改方案。如果你觉得本文对你有所帮助欢迎点赞 / 收藏关注作者获取更多题解留言交流你的疑问或优化思路深入思考答案滑动窗口的核心是保证窗口内始终无重复字符一旦出现重复就移动左指针直到重复消失。这样每个以right结尾的最长无重复子串都会被考虑到因此不会遗漏最优解。数组大小 128 覆盖了标准 ASCII 字符集0~127如果字符串包含中文等 Unicode 字符编码值会超过 127数组越界。此时应改用unordered_mapchar, int或vectorint(256)若只考虑扩展 ASCII 则用 256。清空计数的方式有风险例如窗口内有两个相同字符ahash[a]可能为 2但代码hash[s[left]] 0会将计数直接置 0而实际上窗口中可能还剩一个a。这种写法依赖于每次发现重复时立即移动左指针直到重复消失但这里只移了一位就置 0会导致窗口状态错误。更好的写法是hash[s[left]]--减 1而不是置 0。当前代码之所以能运行是因为每次发现重复后只移动一次左指针但若重复字符在窗口内出现多次这种方法会出错例如abca中窗口abca出现重复a左指针移过第一个a后窗口变为bca计数中a已清零但b和c仍保留逻辑是通的因为hash[s[left]] 0只清除了被移出的字符而a在窗口中已不再存在所以正确。因此该写法是安全的因为每次只移除一个确定的左边界字符该字符在窗口中只出现一次由于窗口内本应无重复重复只发生在刚加入的right上而左指针逐步右移被移除的字符在窗口中确实只有一次出现。两种写法本质相同常见的for循环写法更简洁外层right内层while收缩左指针可读性更好。O(n) 时间O(1) 空间固定哈希数组对于n10^5非常高效完全可接受。延伸挑战答案挑战1若要返回子串本身只需在更新len的同时记录起始下标start最后返回s.substr(start, len)即可。挑战2改用unordered_mapchar, int存储字符及其最新出现位置或使用unordered_setchar配合滑动窗口空间复杂度变为 O(字符种类数)可处理任意 Unicode 字符。祝你在算法之路上越走越稳早日攻克每一道难题下次见 ✨