双指针专题(五)：灵活的起跳——「无重复字符的最长子串」-尧图网站建设

📅 发布时间：2026/6/20 23:24:34

场景想象：你在排队处理一串项链上的珠子（字符串），你的任务是截取一段颜色都不重复的珠子。

右指针 (right)：负责探索，一颗颗把珠子纳入口袋。
左指针 (left)：负责“止损”。
- 一旦右指针发现：“哎呀，这颗红珠子（'a'）我口袋里已经有一颗了！”
- 这时候，左指针不需要一步步往右挪，它可以直接跳到口袋里那颗旧红珠子的后面一位。因为旧红珠子前面的所有区间，只要包含旧红珠子，就一定会有重复，所以统统不要了！

力扣 3. 无重复字符的最长子串

https://leetcode.cn/problems/longest-substring-without-repeating-characters/

题目分析：

输入：字符串s。
目标：找到其中不含有重复字符的最长子串的长度。
输出：长度数值。

例子：s = "abcabcbb"

[abc]: 无重复，长3。
遇到第二个a：重复了！
- 左指针如果不跳，还在第一个a那里，那就是abca（重复）。
- 左指针必须跳过第一个a，来到b的位置。当前窗口变[bca]。
遇到第二个b：
- 左指针跳过旧的b，来到c的位置。当前窗口变[cab]。
...

核心思维：Map 记录索引 + 懒加载跳跃

我们需要一个哈希表 (Map)来记录：“某个字符上一次出现在什么位置（下标）”。

关键逻辑：当right遇到一个字符c，且c在 Map 里存在时：

说明遇到重复了。
我们需要把left更新到Map.get(c) + 1的位置（也就是重复字符的下一位）。
但是！有个惊天大坑：
- 比如abba。
- 遇到第二个b时，left跳到了2(第二个b的位置)。
- 接着遇到第二个a。Map 里记着第一个a在0。
- 如果你直接left = map.get('a') + 1，left会跳回1。
- 这就倒车了！left只能往右走，不能往回退。
- 所以正确的逻辑是：left = Math.max(left, map.get(c) + 1)。

代码实现 (JavaScript)

JavaScript

/** * @param {string} s * @return {number} */ var lengthOfLongestSubstring = function(s) { // 记录字符上一次出现的位置 // key: 字符, value: 索引 index let map = new Map(); let left = 0; let maxLen = 0; for (let right = 0; right < s.length; right++) { const c = s[right]; // 1. 如果 map 里有这个字符，说明可能是重复项 if (map.has(c)) { // 2. 更新左边界 // 核心：只能向右跳，不能倒车！ // 比如 "abba"，遇到第二个 a 时，map.get('a') 是 0，但 left 已经在 2 了 // 所以必须取 max left = Math.max(left, map.get(c) + 1); } // 3. 更新/记录当前字符的最新位置 map.set(c, right); // 4. 更新最大长度 // 当前窗口长度 = right - left + 1 maxLen = Math.max(maxLen, right - left + 1); } return maxLen; };

深度模拟：`"abba"`

right=0('a'): map无。map={a:0}。max=1。
right=1('b'): map无。map={a:0, b:1}。max=2。
right=2('b'):重复！
- map有 'b' (index 1)。
- left = max(0, 1 + 1) = 2。左指针跳到 index 2。
- 此时窗口是b(index 2)。
- 更新map={a:0, b:2}。
- len = 2 - 2 + 1 = 1。max还是 2。
right=3('a'):重复！
- map有 'a' (index 0)。
- left = max(2, 0 + 1)。
- 注意！如果不取 max，left会退回到 1。但我们取 max，所以left保持在 2。
- 逻辑含义：虽然a重复了，但那个旧的a早就被之前的b重复事件给排除在窗口左边了，所以不用管它。
- 更新map={a:3, b:2}。
- len = 3 - 2 + 1 = 2。

总结

这道题的精髓在于：滑动窗口 + 哈希索引优化。普通滑动窗口是left++一步步挪，而这道题利用 Map 实现了left的精准空降。

记住那个坑：left = Math.max(left, map.get(c) + 1)。这是防止“时光倒流”的护身符。

下一题预告：水果成篮

做完了“无重复的最长子串”，下一题LC 904. 水果成篮(Medium) 就是它的孪生兄弟。

题目：你有两个篮子，每个篮子只能装一种类型的水果。
目标：找到最长的连续子序列，使得其中至多包含两种不同的元素。
- 比如[1, 2, 1, 2, 3]-> 最长是[1, 2, 1, 2]，长度 4。一旦遇到 3，就变成三种了，必须扔掉前面的。
这道题其实就是：“至多包含 K 个不同字符的最长子串”（这里 K=2）。

双指针专题(五)：灵活的起跳——「无重复字符的最长子串」

力扣 3. 无重复字符的最长子串

核心思维：Map 记录索引 + 懒加载跳跃

代码实现 (JavaScript)

深度模拟："abba"

总结

深度模拟：`"abba"`