复盘 · LC 3 无重复字符的最长子串

题目

题号：LeetCode 3
名称：无重复字符的最长子串（Longest Substring Without Repeating Characters）
难度：Medium
链接：leetcode.cn/problems/longest-substring-without-repeating-characters
今日代码：3-无重复字符的最长子串/index.js

题意

给字符串 s，求其中不含重复字符的最长子串长度（连续一段，不是子序列）。

子串必须连续；空串答案为 0。
字符集常见为 ASCII；同一字符可在串中多次出现，但不能出现在同一窗口内。

边界：全相同（"aaaa" → 1）、全不同、重复紧挨（"abba"）、重复在窗口左侧更早处（需 i = max(...)，不能无脑跳）。

涉及算法

标签	一句话
滑动窗口	右指针扩窗；遇重复则左边界跳到「上次该字符之后」
哈希表	记字符 → 最近一次下标，O(1) 查冲突

教程对照：07 · 滑动窗口（本篇精讲题之一）。

评价我的解法

思路：j 扫右端，Map 记字符上次下标；撞车则把左端 i 推到 index + 1，并取与当前 i 的较大值。这是标准「最长无重复子串」骨架，且 1036/1036 通过。

我的代码（摘自 3-无重复字符的最长子串/index.js，不含测例与未使用的 subStr）：

javascript

var lengthOfLongestSubstring = function (s) {
  const charMap = new Map();
  let maxSubLen = 0;
  let i = 0,
    j = 0;
  for (j = 0; j < s.length; j++) {
    const c = s[j];
    if (charMap.has(c)) {
      const index = charMap.get(c);
      charMap.delete(c);
      i = Math.max(index + 1, i);
    }
    maxSubLen = Math.max(j - i + 1, maxSubLen);
    charMap.set(c, j);
  }
  maxSubLen = Math.max(j - i, maxSubLen);
  return maxSubLen;
};

对在哪：

右扩左跳 + Math.max(index + 1, i)：避免「更早的旧下标」把左边界往回拽（"abba" 一类能过），这是本题最容易写错的点。
复杂度实质 O(n)：每个下标进窗一次；Map 查询摊还 O(1)。

糙在哪：

charMap.delete(c) 半吊子：删的是当前冲突字符，窗口左侧被甩出去的其它字符仍留在 Map 里。正确性靠后面的 Math.max(..., i) 兜住，不是靠「Map 精确等于当前窗口」。面试口述应说清：要么维护「窗口内集合」并真正踢掉左侧，要么只存「最后出现下标」且用 max——你现在是混搭，能过但解释费劲。
循环后多余一行 maxSubLen = Math.max(j - i, maxSubLen)：循环内已用 j - i + 1 更新过；结束后 j === s.length，j - i 与最后一次窗口长相同（空串也仍是 0）。可删，减干扰。
文件里还有未使用的 subStr 辅助函数，提交前应清掉。

小结：滑窗主菜首发即 AC，比昨天对撞题「先 TLE 再救」更稳。下一步把模板收成「只记 lastIndex + i = max」或「Set 扩缩」二选一，口述干净。

最佳题解

推荐写法：只维护「字符最近下标」，左边界用 max 推进（与你核心一致，去掉 delete 与收尾冗余）：

javascript

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
  const last = new Map();
  let left = 0;
  let ans = 0;
  for (let right = 0; right < s.length; right++) {
    const c = s[right];
    if (last.has(c)) {
      left = Math.max(left, last.get(c) + 1);
    }
    last.set(c, right);
    ans = Math.max(ans, right - left + 1);
  }
  return ans;
};

时间 O(n)，空间 O(min(n, 字符集))。
为何更优：状态语义单一（lastIndex），没有「删一半窗口」的心智负担；边界一眼能讲。

等价写法：用 Set 表示窗口内字符，右扩遇撞则左缩 while 删到不撞——更贴「窗口集合」直觉，常数略差但也好讲。

关联题目

题	为何相关
159. 至多包含两个不同字符的最长子串（会员）	同类滑窗，约束从「无重复」换成「种类数 ≤ k」
340. 至多包含 K 个不同字符的最长子串（会员）	07 篇常见延伸
76. 最小覆盖子串	滑窗另一极：覆盖条件 + 缩到最短
438. 找到字符串中所有字母异位词	定长滑窗 + 频次；今日第二题同族

一句话带走

无重复最长子串：右指针扫，Map 记上次位置，左边界 i = max(i, last+1)，随时更新 j-i+1。

复盘 · LC 3 无重复字符的最长子串 ​

题目 ​

题意 ​

涉及算法 ​

评价我的解法 ​

最佳题解 ​

关联题目 ​

一句话带走 ​