算法图谱

Two Pointers

双指针

技巧核心时间 O(n)空间 O(1)

两个下标相向或同向移动，把 O(n²) 的枚举压成一次扫描。

动画

1
0
2
1
3
2
4
3
5
4
7
5
8
6
9
7

对撞指针：有序数组中是否存在两数之和 = 10

1 / 3

  • 默认

讲解

有序数组两数之和、去重、容器盛水、链表环检测（快慢指针）。

  1. 01对撞：L 在头、R 在尾，根据和的大小收缩某一端。
  2. 02同向：慢指针写、快指针读，原地去重 / 分区。
  3. 03快慢：速度不同，用于中点、环。

易错点

  • 先排序再对撞，否则单调性不成立。
  • 移动指针后注意重复值，避免漏或重。

代码

function twoSumSorted(a, target) {
  let i = class="text-accent">0, j = a.length - class="text-accent">1;
  while (i < j) {
    const s = a[i] + a[j];
    if (s === target) return [i, j];
    if (s < target) i++; else j--;
  }
  return null;
}

相关课题