数组与双指针

讲解

数组是最基础的数据结构：内存连续、下标访问 O(1)、尾部追加均摊 O(1)、中间插入删除 O(n)。它的优势是遍历和随机访问，短板是增删——理解这个性格，才能判断什么时候该用它、什么时候该换结构。

双指针是数组上最常用的问题解决模式，本质是用两个下标的协同移动代替双重循环，把 O(n²) 的枚举压到 O(n)。它有三个经典变体。对撞指针：两个指针从两端向中间走，利用「数组有序」或某种单调性，每一步都能排除一批候选——两数之和（有序版）、盛水最多的容器都是这一类。快慢指针：一个快一个慢，慢指针负责「下一个有效位置」，快指针负责探路——原地移除元素、去重、链表判环都是这一类。分离指针：两个指针分别走两个序列，归并排序的合并阶段、合并两个有序链表是这一类。

以对撞指针为例说清楚「为什么对」：在升序数组里找和为 target 的两个数，若 nums[left] + nums[right] < target，说明 nums[left] 配谁都不够（右边的数只会更小），left 可以直接右移，一步排除了 right - left 个候选对。每一步排除一批，这就是它比暴力枚举快的根本原因。写双指针代码时，始终要能回答「指针为什么可以这样移动而不漏解」。

示例

三个经典题一次走完：有序数组两数之和（对撞指针）、原地移除元素（快慢指针）、盛水最多的容器（对撞指针的进阶形态）：

import assert from 'node:assert/strict';

// 对撞指针：升序数组中找和为 target 的两个下标
function twoSumSorted(nums, target) {
  let left = 0;
  let right = nums.length - 1;
  while (left < right) {
    const sum = nums[left] + nums[right];
    if (sum === target) return [left, right];
    if (sum < target) left++;
    else right--;
  }
  return [-1, -1];
}

// 快慢指针：原地移除所有 val，返回剩余长度
function removeElement(nums, val) {
  let k = 0; // 慢指针：下一个保留位置
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== val) {
      nums[k] = nums[i];
      k++;
    }
  }
  return k;
}

// 对撞指针进阶：盛水最多的容器
// 移动较矮的那根板——因为容积受短板限制，移动长板只会让宽度变小且高度不增
function maxArea(height) {
  let left = 0;
  let right = height.length - 1;
  let best = 0;
  while (left < right) {
    const h = Math.min(height[left], height[right]);
    best = Math.max(best, h * (right - left));
    if (height[left] < height[right]) left++;
    else right--;
  }
  return best;
}

assert.deepStrictEqual(twoSumSorted([2, 7, 11, 15], 9), [0, 1]);
assert.deepStrictEqual(twoSumSorted([2, 3, 4], 6), [0, 2]);
assert.deepStrictEqual(twoSumSorted([1, 2, 3], 100), [-1, -1]);

const arr = [3, 2, 2, 3];
const k = removeElement(arr, 3);
assert.strictEqual(k, 2);
assert.deepStrictEqual(arr.slice(0, k), [2, 2]);

assert.strictEqual(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]), 49);
assert.strictEqual(maxArea([1, 1]), 1);

console.log('双指针三个示例全部通过');

注意 maxArea 的移动规则：宽度只会缩小，想让面积变大只能指望高度变大，所以移动短板——这是「指针移动不漏解」论证的典型形态，面试时主动讲出这层理由会很加分。

常见坑

• 对撞指针用在无序数组上：两端夹逼依赖单调性，无序数组先排序（注意排序会打乱下标，要记录下标就先存值-下标对）。
• 快慢指针改乱了顺序：removeElement 这类写法保证相对顺序，因为它只向前搬运；如果允许乱序可以用「与尾部交换」做到更少的写操作，两题要求不同别混。
• 边界条件写错：while (left < right) 还是 left <= right？对撞指针找一对时用 <，相等时两个指针指向同一元素没有意义。
• 以为双指针只能处理数组：链表的判环、找中点同样是快慢指针，思想完全一致。
• 原地修改后还用旧长度：removeElement 之后只有前 k 个元素有效，后面的是垃圾数据，遍历时用返回值而不是原长度。

小结

数组连续内存、随机访问 O(1)；双指针用指针协同代替双重循环：对撞指针靠单调性排除候选，快慢指针做原地压缩，分离指针做合并。核心修养是能论证「移动指针不漏解」。下一章是它的近亲：滑动窗口。