数组与双指针（5 题）

面试统一用 JavaScript（Node 18+）。每题先自己写，再看答案。 返回目录：4.algorithms/题单.md

1. 两数之和

题意：在数组里找两个数，和等于 target，返回下标。 思路：哈希表存「值 -> 下标」，遍历时先查 target - v 出现过没有。 复杂度：时间 O(n)，空间 O(n)。 易错：必须先查再存，否则同一个元素会被用两次（[3,3] 会返回 [1,1]）。 追问：「数组有序怎么办？」——有序就用双指针，空间 O(1)。

function twoSum(nums, target) {
  const seen = new Map(); // 值 -> 下标
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (seen.has(need)) return [seen.get(need), i];
    seen.set(nums[i], i);
  }
  return [];
}

2. 三数之和

题意：找出所有和为 0 且不重复的三元组。 思路：排序 + 固定第一个数 + 双指针夹逼。去重是这题的全部难点。 复杂度：时间 O(n^2)，空间 O(1)（不算结果）。 易错：三处去重——外层 i 跳过重复、找到解后 l 和 r 各自跳过重复。 易错：JS 的 sort() 默认按字符串排序，必须传 (a, b) => a - b。

function threeSum(nums) {
  nums.sort((a, b) => a - b); // 必须给比较函数，否则 -1 会排在 -4 前面
  const res = [];
  const n = nums.length;
  for (let i = 0; i < n - 2; i++) {
    if (nums[i] > 0) break; // 最小的都大于 0，后面不可能凑出 0
    if (i > 0 && nums[i] === nums[i - 1]) continue; // 去重 1：外层
    let l = i + 1;
    let r = n - 1;
    while (l < r) {
      const sum = nums[i] + nums[l] + nums[r];
      if (sum === 0) {
        res.push([nums[i], nums[l], nums[r]]);
        while (l < r && nums[l] === nums[l + 1]) l++; // 去重 2
        while (l < r && nums[r] === nums[r - 1]) r--; // 去重 3
        l++;
        r--;
      } else if (sum < 0) {
        l++;
      } else {
        r--;
      }
    }
  }
  return res;
}

3. 移动零

题意：把所有 0 移到末尾，同时保持非零元素的相对顺序。 思路：快慢指针。慢指针指向「下一个要放非零元素」的位置。 复杂度：时间 O(n)，空间 O(1)。 易错：用交换而不是覆盖，天然保持非零元素顺序。 追问：「最少写操作次数？」——覆盖 + 最后补零，非零元素只写一次。

function moveZeroes(nums) {
  let slow = 0; // slow 左边全是非零，且顺序不变
  for (let fast = 0; fast < nums.length; fast++) {
    if (nums[fast] !== 0) {
      [nums[slow], nums[fast]] = [nums[fast], nums[slow]];
      slow++;
    }
  }
}

4. 盛最多水的容器

题意：两条竖线和 x 轴围成容器，求最大面积。 思路：双指针从两端向中间收，每次移动较矮的那一边。 复杂度：时间 O(n)，空间 O(1)。 易错：为什么移动矮的？面积由矮边决定，移动高边只会让宽度变小、高度不会变大。

function maxArea(height) {
  let l = 0;
  let r = height.length - 1;
  let best = 0;
  while (l < r) {
    const h = Math.min(height[l], height[r]);
    best = Math.max(best, h * (r - l));
    if (height[l] < height[r]) l++;
    else r--;
  }
  return best;
}

5. 除自身以外数组的乘积

题意：返回数组，每个位置是除自己外所有元素的乘积。要求 O(n) 且不能用除法。 思路：前后缀分解。先从左往右把前缀积存进结果，再从右往左乘上后缀积。 复杂度：时间 O(n)，空间 O(1)（输出数组不算额外空间）。 易错：不能用除法是因为数组里可能有 0，除法会失效。

function productExceptSelf(nums) {
  const n = nums.length;
  const res = new Array(n).fill(1);
  // 第一遍：res[i] = nums[0..i-1] 的乘积
  for (let i = 1; i < n; i++) {
    res[i] = res[i - 1] * nums[i - 1];
  }
  // 第二遍：right 是 nums[i+1..n-1] 的乘积
  let right = 1;
  for (let i = n - 1; i >= 0; i--) {
    res[i] *= right;
    right *= nums[i];
  }
  return res;
}