LeetCode热题100：3. 无重复字符的最长子串

简介

题目链接：https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/?envType=problem-list-v2&envId=2cktkvj

解决方式：滑动窗口（双指针 + 哈希）

这是作者学习众多大神的思路进行解题的步骤，很推荐大家解题的时候去看看题解里面大佬们的思路、想法！

推荐看powcai大佬的讲解，其中包含了一系列问题，如：最小覆盖子串、无重复字符的最长子串、至多包含两个不同字符的最长子串等。

滑动窗口

classSolution{// 滑动窗口--双指针与哈希的结合// 双指针很难解决多个元素的一个状态或者差异// 此处对于无重复子串的判断涉及到多个位，双指针无法或者很难办到// 这时候就可以借助哈希存储一定的规则信息来解决publicintlengthOfLongestSubstring(Strings){// 哈希，存储迭代过程中的信息Map<Character,Integer>map=newHashMap<>();// 特例if(s==null||s.length()==0)return0;intmax=0;// 双指针intleft=0;// 右指针，同时遍历字符for(intright=0;right<s.length();right++){if(map.containsKey(s.charAt(right))){// 如果当前迭代的元素处于滑动窗口中，则将左指针跳到重复元素的右边，即重复元素索引 + 1// 之所以可以这样，是因为在没有重复元素之前迭代的过程已经把不重复的最大子串的长度记下了// 跳到滑动窗口中重复元素的右边，开始新一轮的查找// 看看是否还有必之前的记录还大的不重复的子串left=Math.max(left,map.get(s.charAt(right))+1);// 确保左指针不会回退，即出现以前存在过的元素时左指针跳转回滑动窗口已经抛弃的部分}// 哈希，存放字符以及对应的索引，方便判断元素是否重复map.put(s.charAt(right),right);// 每次迭代都需存储当前无重复子串中较大的那个，为了查到最大的那一位max=Math.max(max,(right-left)+1);}returnmax;}}

讲解

// left= Math.max(left, map.get(s.charAt(right)) + 1);// 确保左指针不会回退，即出现以前存在过的元素时左指针跳转回滑动窗口已经抛弃的部分left=map.get(s.charAt(right))+1;

这个代码在处理"abba"这个测试用例时确实会输出3，而正确答案应该是2（最长无重复子串是 “ab” 或 “ba”）。

问题出在这一行：

这行代码的逻辑是：当遇到重复字符时，把左指针直接跳到「上一次出现该字符的位置」的下一位。

这个逻辑在大多数情况下是对的，但有一个致命缺陷：
它没有保证 left 只能向右移动，而不会回退！

即，在 right=3 时，执行：

left=map.get('a')+1;// map.get('a') 还是 0！所以 left = 1

此时窗口变成 [1,3] → 对应子串是 “bba”，长度 3！

然后计算：

max=Math.max(max,right-left+1)=Math.max(2,3-1+1)=3

所以最终返回了 3！这就是 bug 所在。

根本原因：

当遇到第二个 ‘a’ 时，map 中存的还是第一次出现的 ‘a’ 的位置（索引 0），于是你把 left 跳到 1，但实际上你当前的窗口左边界已经移动到 2 了，你却把它拉回到了 1，这就导致窗口错误地包含了（跳转到）之前已经“丢弃”的字符。

正确做法：

left 不能回退！

标准写法是：

left=Math.max(left,map.get(s.charAt(right))+1);

这样就能保证 left 只向右移动，不会倒退。

总结

出错的那一行是：

left=map.get(s.charAt(right))+1;// 错误！可能导致 left 回退

应该改成：

left=Math.max(left,map.get(s.charAt(right))+1);// 正确！

这就是 LeetCode 3. 无重复字符的最长子串 经典滑动窗口的正确写法。

记住：滑动窗口的左指针永远只能右移，不能左移。

创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考