滑动窗口与区间（5 题）

通用模板：右指针扩张 -> 满足条件时左指针收缩 -> 过程中更新答案。 返回目录：4.algorithms/题单.md

1. 无重复字符的最长子串

题意：求不含重复字符的最长子串长度。 思路：哈希表记录字符最后出现的位置，左指针只能往右跳，不能往左退。 复杂度：时间 O(n)，空间 O(字符集)。 易错：收缩左指针前必须判断 idx >= left，否则会往回跳（如 "abba"）。 追问：「字符集很大怎么办？」——用 Map 存位置，一样是 O(n)。

function lengthOfLongestSubstring(s) {
  const last = new Map(); // 字符 -> 最后出现的下标
  let left = 0;
  let best = 0;
  for (let right = 0; right < s.length; right++) {
    const idx = last.get(s[right]);
    if (idx !== undefined && idx >= left) left = idx + 1;
    last.set(s[right], right);
    best = Math.max(best, right - left + 1);
  }
  return best;
}

2. 找到字符串中所有字母异位词

题意：找出 s 中所有是 p 的字母异位词的起始下标。 思路：固定长度窗口 + 计数数组。Go 的数组可以直接用 == 比较，JS 不行，所以额外维护一个 diff（还有几个桶的数量对不上）。 复杂度：时间 O(n)，空间 O(1)（26 个字母的计数数组）。 易错：窗口长度固定为 p.length；diff 要在移入和移出时各更新一次。

function findAnagrams(s, p) {
  const res = [];
  const n = s.length;
  const m = p.length;
  if (n < m) return res;

  const cnt = new Array(26).fill(0); // 窗口计数 - 目标计数
  for (let i = 0; i < m; i++) {
    cnt[s.charCodeAt(i) - 97]++;
    cnt[p.charCodeAt(i) - 97]--;
  }
  let diff = 0; // 不为 0 的桶个数
  for (let i = 0; i < 26; i++) if (cnt[i] !== 0) diff++;
  if (diff === 0) res.push(0);

  for (let i = m; i < n; i++) {
    let c = s.charCodeAt(i) - 97; // 移入
    if (cnt[c] === 0) diff++;
    cnt[c]++;
    if (cnt[c] === 0) diff--;

    c = s.charCodeAt(i - m) - 97; // 移出
    if (cnt[c] === 0) diff++;
    cnt[c]--;
    if (cnt[c] === 0) diff--;

    if (diff === 0) res.push(i - m + 1);
  }
  return res;
}

3. 最小覆盖子串

题意：s 中覆盖 t 所有字符的最短子串，没有则返回空串。 思路：可变窗口 + missing 计数。need 允许为负，表示窗口里该字符多了。 复杂度：时间 O(n)，空间 O(字符集)。 易错：收缩条件写成 while (missing === 0)，先更新答案再收缩左边界。

function minWindow(s, t) {
  if (s.length < t.length) return "";

  const need = new Map(); // 还差多少个该字符
  for (const ch of t) need.set(ch, (need.get(ch) || 0) + 1);

  let missing = t.length;
  let bestL = 0;
  let bestLen = Infinity;
  let left = 0;

  for (let right = 0; right < s.length; right++) {
    const c = s[right];
    if ((need.get(c) || 0) > 0) missing--; // 这个字符确实还差，才算补上一个
    need.set(c, (need.get(c) || 0) - 1);

    while (missing === 0) {
      if (right - left + 1 < bestLen) {
        bestL = left;
        bestLen = right - left + 1;
      }
      const d = s[left]; // 收缩左边界
      need.set(d, need.get(d) + 1);
      if (need.get(d) > 0) missing++;
      left++;
    }
  }
  return bestLen === Infinity ? "" : s.slice(bestL, bestL + bestLen);
}

4. 合并区间

题意：合并所有重叠的区间。 思路：按左端点排序，然后一次遍历合并。 复杂度：时间 O(n log n)（排序），空间 O(1)（不算结果）。 易错：判断不重叠用 last[1] < iv[0]，注意是严格小于（端点相等算重叠）。

function merge(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  const res = [];
  for (const iv of intervals) {
    const last = res[res.length - 1];
    if (!last || last[1] < iv[0]) {
      res.push([iv[0], iv[1]]); // 不重叠，开新区间
    } else {
      last[1] = Math.max(last[1], iv[1]); // 重叠，只扩右端点
    }
  }
  return res;
}

5. 轮转数组

题意：把数组右移 k 位，要求原地修改。 思路：三次翻转——整体翻转、前 k 个翻转、剩下翻转。 复杂度：时间 O(n)，空间 O(1)。 易错：k 要先对 n 取模，否则 k > n 时下标越界；n 为 0 要提前返回（取模会得到 NaN）。 追问：「还有别的写法吗？」——新建数组 (i + k) % n 最简单，但空间 O(n)。

function rotate(nums, k) {
  const n = nums.length;
  if (n === 0) return;
  k %= n;
  const reverse = (i, j) => {
    while (i < j) {
      [nums[i], nums[j]] = [nums[j], nums[i]];
      i++;
      j--;
    }
  };
  reverse(0, n - 1);
  reverse(0, k - 1);
  reverse(k, n - 1);
}