无重复字符的最长子串

更新: 7/3/2026 字数: 0 字 时长: 0 分钟

LeetCode 第 3 题 · 中等 · 高频面试题（滑动窗口经典入门）

题目描述

给定一个字符串 s，请你找出其中不含有重复字符的最长子串的长度。

什么是「子串」？

子串（substring）必须是连续的一段，例如 "abc" 的子串有 "a"、"ab"、"bc" 等，但 "ac" 不是子串（不连续，那叫子序列）。

示例：

输入	输出	说明
"abcabcbb"	3	最长无重复子串是 "abc"
"bbbbb"	1	最长无重复子串是 "b"
"pwwkew"	3	最长无重复子串是 "wke"（注意 "pwke" 是子序列，不是子串）
""	0	空串

思路拆解：从暴力到最优

第一步：暴力枚举（先把问题解出来）

最直接的想法——枚举所有子串，逐个检查是否含重复字符，记录最长的那个。

• 用两层循环确定子串的起点 i 和终点 j；
• 对每个子串 s[i..j]，用一个集合判断是否有重复字符。

这样能得到正确答案，但每次都要重新检查一段区间，做了大量重复劳动，时间复杂度高达 （枚举 个子串，每次检查 ）。

点击展开暴力解法（仅供理解，不推荐）

function lengthOfLongestSubstring_bruteForce(s) {
  const hasRepeat = (str, start, end) => {
    const set = new Set();
    for (let k = start; k <= end; k++) {
      if (set.has(str[k])) return true; // 出现重复
      set.add(str[k]);
    }
    return false;
  };

  let best = 0;
  for (let i = 0; i < s.length; i++) {
    for (let j = i; j < s.length; j++) {
      if (!hasRepeat(s, i, j)) {
        best = Math.max(best, j - i + 1);
      }
    }
  }
  return best;
}

第二步：发现规律，优化为滑动窗口

暴力法的浪费在于：当我们检查 s[i..j] 时，其实已经知道 s[i..j-1] 是否无重复了，没必要从头再算。

关键观察：我们维护一个「窗口」[left, right]，保证窗口内永远没有重复字符。

• 让 right 不断向右扩张，把新字符纳入窗口；
• 如果新字符 s[right] 在窗口内已经出现过，就把 left 向右移动，直到窗口内不再重复；
• 每一步都用当前窗口长度 right - left + 1 更新答案。

这就是滑动窗口：left 和 right 都只会向右走，两个指针合计最多移动 步。

核心思路

用一个哈希表记录「每个字符最近一次出现的下标」。当 right 遇到重复字符 c 时，直接把 left 跳到 map[c] + 1，一步到位跳过所有冲突，无需逐格收缩。这样整个过程只需遍历一遍字符串，时间复杂度降到 。

窗口收缩的判定条件是本题最容易写错的地方：只有当重复字符的位置在当前窗口内（即 map[c] >= left）时，才需要移动 left。

交互式动画演示

下面用样例 "abcabcbb" 完整演示滑动窗口的每一步。点击 下一步 / 自动播放 观察 left、right 指针的移动、哈希表的变化与 max 的刷新：

滑动窗口 · 无重复最长子串演示

样例输入："abcabcbb"

a0

b1

c2

a3

b4

c5

b6

b7

窗口空

当前长度0

max0

哈希表（字符 → 最近下标）

（空）

初始化：left = 0，right 尚未进入，最大长度 max = 0。

步骤 0 / 9

观察重点

• 绿色 L 是左边界，蓝色 R 是右边界，高亮区域就是当前无重复窗口；
• 当 R 指向的字符在窗口里重复时，L 会跳跃到重复位的下一格（黄色旁白提示）；
• max 只增不减，始终记录见过的最长窗口。

完整代码（JavaScript）

/**
 * 无重复字符的最长子串 —— 滑动窗口 + 哈希表
 * @param {string} s
 * @return {number}
 */
function lengthOfLongestSubstring(s) {
  const map = new Map(); // 字符 -> 该字符最近一次出现的下标
  let left = 0;          // 窗口左边界
  let best = 0;          // 结果：最长无重复子串长度

  for (let right = 0; right < s.length; right++) {
    const c = s[right];
    // 关键：仅当重复字符落在【当前窗口内】时，才收缩左边界
    // map.get(c) >= left 保证不会把 left 往回拨
    if (map.has(c) && map.get(c) >= left) {
      left = map.get(c) + 1; // 一步跳到重复位的下一格
    }
    map.set(c, right);       // 更新该字符的最新下标

    // 当前窗口 [left, right] 一定无重复，更新答案
    const curLen = right - left + 1;
    if (curLen > best) best = curLen;
  }

  return best;
}

// 测试
console.log(lengthOfLongestSubstring('abcabcbb')); // 3
console.log(lengthOfLongestSubstring('bbbbb'));    // 1
console.log(lengthOfLongestSubstring('pwwkew'));   // 3
console.log(lengthOfLongestSubstring(''));         // 0

复杂度分析

解法	时间复杂度	空间复杂度	说明
暴力枚举			枚举 个子串，每次检查
滑动窗口 + 哈希表			每个字符最多被 left、right 各访问一次

其中 为字符串长度， 为字符集大小（如纯 ASCII 时 ）。空间复杂度取二者较小值：哈希表最多存储 个不同字符。

边界与易错点

易错点清单

1. 空串与单字符：s = "" 应返回 0，s = "a" 应返回 1。循环从 best = 0 起步天然覆盖。
2. left 只能前进，不能后退：必须判断 map.get(c) >= left。否则遇到 "abba" 时会出错——处理到第二个 a 时，map 里 a 的旧下标是 0，若不判断就会把 left 拨回 1，导致窗口包含重复的 b。
3. 更新 map 的时机：先根据旧记录移动 left，再写入当前字符的新下标，顺序不能颠倒。
4. 窗口长度公式：是 right - left + 1，别漏掉 + 1。
5. 字符集范围：若题目允许 Unicode / emoji，用 Map 比用固定长度数组更稳妥。

一句话记忆

右指针负责「探路扩张」，哈希表负责「记住谁在哪」，左指针负责「遇到重复就跳到冲突点之后」——三者配合，一次遍历搞定。