[!info] related notes

• 所属 MOC: 算法面试题型 MOC
• 相关模式: 滑动窗口模板
• 原理: 滑动窗口

最长无重复字符子串

一句话定义

给定一个字符串，找出其中不包含重复字符的最长连续子串的长度。

---

题目

输入: s = "abcabcbb"
输出: 3
解释: 最长无重复子串是 "abc"，长度 3

输入: s = "bbbbb"
输出: 1
解释: 最长无重复子串是 "b"，长度 1

输入: s = "pwwkew"
输出: 3
解释: 最长无重复子串是 "wke"，长度 3

---

解法：滑动窗口 + 哈希表

思路

用双指针维护一个窗口，用 Map 记录每个字符最后出现的位置。

• 右指针扩展窗口，遇到重复字符时收缩左指针
• 维护 maxLen 更新最大值

代码

function lengthOfLongestSubstring(s) {
  const map = new Map();
  let maxLen = 0;
  let left = 0;
  
  for (let right = 0; right < s.length; right++) {
    // 如果字符已存在且在窗口内，移动左指针
    if (map.has(s[right]) && map.get(s[right]) >= left) {
      left = map.get(s[right]) + 1;
    }
    
    // 更新字符位置
    map.set(s[right], right);
    
    // 更新最大长度
    maxLen = Math.max(maxLen, right - left + 1);
  }
  
  return maxLen;
}

上面的 JavaScript 按 UTF-16 代码单元索引；对题目常见的英文字母、数字和符号输入可直接使用。若要按 Unicode 码点处理，需先转为码点序列；用户感知字符还涉及组合字符分段。

复杂度

• 时间：O(n)
• 空间：O(min(m, n))，m 是字符集大小

---

面试回答要点

1. 滑动窗口：双指针维护无重复窗口
2. 哈希表：记录字符最后出现位置，快速判断重复
3. 左指针跳转：遇到重复时，左指针直接跳到上次出现位置的右边
4. 时间 O(n)：每个字符最多访问两次

---

变形题

• 返回最长子串本身
• 允许 k 个重复字符
• 字节流/数字数组版本