无重复字符的最长子串

题目描述

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

示例

示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

我的解题过程

第一次尝试 - 滑动窗口 + Set

一开始想的是用两个指针来表示当前的子串范围（也就是滑动窗口），然后不断移动右指针扩展子串。

我的思路是：

• 用一个 Set 来存当前窗口里的字符，方便判断是否重复
• 右指针不断往右移动，遇到没见过的字符就加进去
• 如果遇到重复字符了，就移动左指针，把窗口左边的字符一个个删掉
• 每次都记录一下当前窗口的最大长度

function lengthOfLongestSubstring(s: string): number {
  let left = 0;
  let right = 0;
  let maxLength = 0;
  const charSet = new Set<string>();

  while (right < s.length) {
    const char = s[right];
    if (!charSet.has(char)) {
      charSet.add(char);
      right++;
      maxLength = Math.max(maxLength, right - left);
    } else {
      charSet.delete(s[left]);
      left++;
    }
  }

  return maxLength;
}

这个方法能解决问题，但其实有点慢。因为遇到重复字符时，左指针是一个一个往右移的，可能会移动好几次。

参考优秀题解的改进 - 滑动窗口 + Map

后面看了其他人的题解，发现可以用 Map 来记录每个字符最后出现的位置。这样遇到重复字符时，可以直接把左指针跳到重复字符上次出现位置的下一个位置，而不用一个一个移动。

关键的改进点：

• 用 Map 存字符和它的索引位置
• 遇到重复字符时，直接把 left 跳到 Math.max(left, map.get(char) + 1)
• 这样可以一次性跳过所有重复的部分

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

  for (let right = 0; right < s.length; right++) {
    const char = s[right];

    if (map.has(char)) {
      // 如果字符重复了，left 要跳到重复字符上次出现位置的下一个
      // 但不能往回跳，所以要取 max
      left = Math.max(left, map.get(char)! + 1);
    }

    map.set(char, right);
    maxLength = Math.max(maxLength, right - left + 1);
  }

  return maxLength;
}

这样写效率就高多了，左指针不用一个一个移动了。

小结

这道题是经典的滑动窗口问题。几个关键点：

1. 滑动窗口的本质：用两个指针维护一个不重复字符的窗口，右指针扩展窗口，左指针收缩窗口
2. 重复判断：用 Set 或 Map 来快速判断字符是否重复
3. 优化思路：用 Map 记录字符位置，可以让左指针直接跳到合适的位置，避免重复移动
4. 边界处理：left = Math.max(left, map.get(char)! + 1) 这里的 Math.max 很重要，因为左指针不能往回跳

滑动窗口这个思路在很多字符串、数组题目里都能用上，掌握了这个套路后面很多题都好做了。