跳到主要内容

无重复字符的最长子串

问题​

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

示例：

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

输入：s = "bbbbb"
输出：1

输入：s = "pwwkew"
输出：3
解释：最长无重复子串是 "wke"，长度为 3
注意 "pwke" 是子序列而不是子串

来源：LeetCode 3. 无重复字符的最长子串

子串 vs 子序列
  • 子串（substring）：连续的字符序列，如 "abc" 是 "abcde" 的子串
  • 子序列（subsequence）：可以不连续，如 "ace" 是 "abcde" 的子序列

答案​

方法一：滑动窗口 + Set（推荐）​

核心思路：维护一个「窗口」，用 Set 记录窗口内的字符。右指针扩展窗口，遇到重复字符时左指针收缩窗口，直到没有重复。

lengthOfLongestSubstringSet.ts
function lengthOfLongestSubstring(s: string): number {
  const set = new Set<string>();
  let left = 0;
  let maxLen = 0;

  for (let right = 0; right < s.length; right++) {
    // 如果窗口内有重复字符，收缩左边界
    while (set.has(s[right])) {
      set.delete(s[left]);
      left++;
    }

    // 将当前字符加入窗口
    set.add(s[right]);

    // 更新最大长度
    maxLen = Math.max(maxLen, right - left + 1);
  }

  return maxLen;
}

图解过程：

s = "abcabcbb"

right=0: 'a' → set={a}, window="a",        maxLen=1
right=1: 'b' → set={a,b}, window="ab",     maxLen=2
right=2: 'c' → set={a,b,c}, window="abc",  maxLen=3
right=3: 'a' → 重复！收缩 left: 删 'a'，left=1
          set={b,c,a}, window="bca",        maxLen=3
right=4: 'b' → 重复！收缩 left: 删 'b'，left=2
          set={c,a,b}, window="cab",        maxLen=3
right=5: 'c' → 重复！收缩 left: 删 'c'，left=3
          set={a,b,c}, window="abc",        maxLen=3
right=6: 'b' → 重复！收缩 left: 删 'a'，left=4
          still 重复！删 'b'，left=5
          set={c,b}, window="cb",           maxLen=3
right=7: 'b' → 重复！收缩 left: 删 'c'，left=6
          still 重复！删 'b'，left=7
          set={b}, window="b",              maxLen=3

结果：3
复杂度分析
  • 时间复杂度：O(n)O(n) — 左右指针各遍历一次
  • 空间复杂度：O(k)O(k) — k 是字符集大小（英文字母最多 128）

方法二：滑动窗口 + Map（优化版，最推荐）​

优化点：当遇到重复字符时，直接将 left 跳到重复字符上次出现位置的下一个，避免逐步收缩。

lengthOfLongestSubstringMap.ts
function lengthOfLongestSubstring(s: string): number {
  const map = new Map<string, number>(); // 字符 -> 最后出现的索引
  let left = 0;
  let maxLen = 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;
}

图解优化效果：

s = "abcabcbb"

right=0: 'a' → map={a:0}, left=0, maxLen=1
right=1: 'b' → map={a:0,b:1}, left=0, maxLen=2
right=2: 'c' → map={a:0,b:1,c:2}, left=0, maxLen=3
right=3: 'a' → 'a' 在 map 中且 index(0) >= left(0)
  left 直接跳到 0+1=1 （不用逐步收缩！）
  map={a:3,b:1,c:2}, left=1, maxLen=3
...
为什么要判断 map.get(s[right])! >= left？

因为 Map 中可能保留之前窗口外的旧索引。如果旧索引在 left 之前，说明那个重复字符已经不在当前窗口内了，不需要移动 left。

方法三：使用数组代替 Map（ASCII 优化）​

如果字符集是 ASCII（128 个字符），可以用数组替代 Map，更快：

lengthOfLongestSubstringArray.ts
function lengthOfLongestSubstring(s: string): number {
  // 记录每个字符最后出现的位置，-1 表示未出现
  const lastIndex = new Array(128).fill(-1);
  let left = 0;
  let maxLen = 0;

  for (let right = 0; right < s.length; right++) {
    const charCode = s.charCodeAt(right);

    if (lastIndex[charCode] >= left) {
      left = lastIndex[charCode] + 1;
    }

    lastIndex[charCode] = right;
    maxLen = Math.max(maxLen, right - left + 1);
  }

  return maxLen;
}
性能差异

数组访问比 Map 快，因为不需要哈希计算。在 LeetCode 上通常能快 20-30%。

方法四：暴力法（不推荐）​

枚举所有子串，检查是否有重复字符：

lengthOfLongestSubstringBrute.ts
function lengthOfLongestSubstring(s: string): number {
  let maxLen = 0;

  for (let i = 0; i < s.length; i++) {
    const seen = new Set<string>();
    for (let j = i; j < s.length; j++) {
      if (seen.has(s[j])) break;
      seen.add(s[j]);
      maxLen = Math.max(maxLen, j - i + 1);
    }
  }

  return maxLen;
}
复杂度
  • 时间复杂度：O(n2)O(n^2) — 会超时
  • 空间复杂度：O(k)O(k)

常见面试追问​

Q1: 滑动窗口模板是什么？​

答案：滑动窗口的通用模板如下，适用于子串/子数组类问题：

function slidingWindow(s: string): number {
  const window = new Map<string, number>();
  let left = 0;
  let result = 0;

  for (let right = 0; right < s.length; right++) {
    // 1. 扩展窗口：将 s[right] 加入窗口
    const c = s[right];
    window.set(c, (window.get(c) || 0) + 1);

    // 2. 收缩窗口：当窗口不满足条件时，移动左指针
    while (/* 窗口不满足条件 */) {
      const d = s[left];
      // 将 s[left] 从窗口移出
      window.set(d, window.get(d)! - 1);
      left++;
    }

    // 3. 更新答案
    result = Math.max(result, right - left + 1);
  }

  return result;
}

Q2: 如何找到所有最长无重复子串？​

答案：

function allLongestSubstrings(s: string): string[] {
  const map = new Map<string, number>();
  let left = 0;
  let maxLen = 0;
  const results: string[] = [];

  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);

    const len = right - left + 1;
    if (len > maxLen) {
      maxLen = len;
      results.length = 0; // 清空
      results.push(s.substring(left, right + 1));
    } else if (len === maxLen) {
      results.push(s.substring(left, right + 1));
    }
  }

  return results;
}

Q3: 最多包含 K 个不同字符的最长子串？(LeetCode 340)​

答案：

function lengthOfLongestSubstringKDistinct(
  s: string,
  k: number
): number {
  const map = new Map<string, number>();
  let left = 0;
  let maxLen = 0;

  for (let right = 0; right < s.length; right++) {
    map.set(s[right], (map.get(s[right]) || 0) + 1);

    while (map.size > k) {
      const c = s[left];
      map.set(c, map.get(c)! - 1);
      if (map.get(c) === 0) map.delete(c);
      left++;
    }

    maxLen = Math.max(maxLen, right - left + 1);
  }

  return maxLen;
}

Q4: 这道题在前端的实际应用？​

答案：

  • 输入验证：检测密码中连续不重复字符的长度
  • 文本处理：找出文本中不含重复单词的最长段落
  • URL 去重：在 URL 参数中找不重复的键

相关链接​