手帐 Blog

主题

05 · 对撞双指针 ​

目标：默写「左右指针从两端往中间走」模板。
精讲 167、11、15 三题，能口述三数之和的去重思路。

1. 为什么面试考 ​

  • 有序数组上，双指针常把 O(n²) 暴力 压成 O(n)。
  • 前端笔试 / 一面高频：两数之和 II、盛水容器、三数之和。
  • 考你能不能 根据单调性决定移动哪一侧，而不是死记答案。

2. 零基础概念 ​

对撞双指针：left = 0，right = n - 1，两指针向中间靠拢。

[ 1,  2,  3,  4,  5 ]
  ↑                 ↑
 left             right

什么时候用？

信号例子
数组已排序（或先排序）167、15
问「两端的组合」11 盛水
移动一侧能排除一批答案和太大 → right--

和太大 / 太小怎么动？

  • 当前和 > target → 右边太大 → right--
  • 当前和 < target → 左边太小 → left++
  • 当前和 = target → 记录答案，再移动（题目要求决定移哪边）

3. JS 模板（对撞双指针） ​

javascript
function collideTwoPointers(arr, check) {
  let left = 0
  let right = arr.length - 1

  while (left < right) {
    const result = check(arr, left, right)
    if (result === 0) {
      // 找到目标：按题意处理 left/right，常见是都移动或只移一边
      left++
      right--
    } else if (result < 0) {
      left++
    } else {
      right--
    }
  }
}

check 返回三态：负数 = 当前组合「太小」，正数 = 「太大」，0 = 「刚好」。

4. 精讲 · 167 两数之和 II（有序数组） ​

题意：升序数组，找两数之和 = target，返回下标（1-based）。

套路：经典对撞。和大了移右，和小了移左。

javascript
/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (numbers, target) {
  let left = 0
  let right = numbers.length - 1

  while (left < right) {
    const sum = numbers[left] + numbers[right]
    if (sum === target) {
      return [left + 1, right + 1]
    }
    if (sum < target) {
      left++
    } else {
      right--
    }
  }

  return [-1, -1]
}

边界：题目保证有解；若无解可返回 [-1, -1]。

5. 精讲 · 11 盛最多水的容器 ​

题意：竖线高度数组，选两条线与 x 轴围成容器，求最大面积。

直觉：面积 = min(h[left], h[right]) * (right - left)。
宽度一定变窄，所以 移动较短的那一侧——较短侧留着也换不来更大面积。

javascript
/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function (height) {
  let left = 0
  let right = height.length - 1
  let ans = 0

  while (left < right) {
    const w = right - left
    const h = Math.min(height[left], height[right])
    ans = Math.max(ans, w * h)

    if (height[left] < height[right]) {
      left++
    } else {
      right--
    }
  }

  return ans
}

口述一句：宽变窄后，只有换更高的边才可能更大 → 移矮边。

6. 精讲 · 15 三数之和（排序 + 去重） ​

题意：找所有和为 0 的三元组，不重复。

套路：

  1. 先 排序。
  2. 固定 i，在 [i+1, n-1] 上对撞找 -nums[i]。
  3. 去重 三处：固定 i 跳过相同值；找到答案后 left/right 也跳过相同值。
javascript
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
  nums.sort((a, b) => a - b)
  const ans = []
  const n = nums.length

  for (let i = 0; i < n - 2; i++) {
    // 去重：同一个 nums[i] 只当一次「第一个数」
    if (i > 0 && nums[i] === nums[i - 1]) continue
    if (nums[i] > 0) break // 后面都 ≥0，不可能和为 0

    let left = i + 1
    let right = n - 1
    const need = -nums[i]

    while (left < right) {
      const sum = nums[left] + nums[right]
      if (sum === need) {
        ans.push([nums[i], nums[left], nums[right]])
        left++
        right--
        // 去重：同一轮里跳过重复的 left / right
        while (left < right && nums[left] === nums[left - 1]) left++
        while (left < right && nums[right] === nums[right + 1]) right--
      } else if (sum < need) {
        left++
      } else {
        right--
      }
    }
  }

  return ans
}

去重口诀：

位置写法
固定 ii > 0 && nums[i] === nums[i-1] → continue
找到一组后left/right 各自 while 跳过相同值

复杂度：排序 O(n log n) + 双指针 O(n²)。

7. 练习清单 ​

题号名称难度备注
167两数之和 IIEasy本篇已精讲
11盛最多水的容器Medium本篇已精讲
15三数之和Medium本篇已精讲
16最接近的三数之和Medium固定 i + 对撞，记录最接近
18四数之和Medium两层固定 + 对撞，去重同 15

8. 今日验收 ​

  • [ ] 不看代码，默写 167 的 while (left < right) 三分支
  • [ ] 能解释 11 为什么移 较短 边
  • [ ] 能口述 15 的三处去重
  • [ ] LeetCode 提交 167、11、15 至少各 1 次 AC

9. 可选 · 记忆唤醒 ​

对撞：left=0, right=n-1
和 vs target：大了 right--，小了 left++
盛水：移矮边
三数之和：排序 → 固定 i → 对撞 → i/left/right 去重

下一步 ​

→ 06 · 同向双指针与快慢指针