双指针
双指针可以在有序数组中寻找和等于目标的两个元素。把两个下标放在数组两端，比较当前和与目标，再排除不可能参与答案的一端。一次扫描即可完成，时间复杂度为 O(n)，额外空间为 O(1)。
有序性让一次比较排除一批配对。如果两端之和太大，右端与区间内其他元素相加也会太大，因为当前左端已经是最小值。如果两端之和太小，左端与其他元素相加也达不到目标，因为当前右端已经是最大值。每次移动都在排除一整行或一整列候选配对。
双指针如何工作
初始候选区间为 [lo, hi]，其中 lo = 0、hi = n − 1。每轮执行三步：
- 读取两端，计算
sum = nums[lo] + nums[hi]。 - 比较
sum与target。 - 相等就返回
[lo, hi]。sum < target时令lo += 1；sum > target时令hi −= 1。
循环条件是 lo < hi，保证使用两个不同位置。没有命中时，每轮排除一个端点，最多移动 n − 1 次。指针相遇仍未找到配对，就返回 [-1, -1]。
为什么可以排除一个端点
当 sum > target 时，nums[hi] 是 nums[lo..hi] 的最大值，nums[lo] 是最小值。把右端与区间内任意其他值配对，和都不小于当前和，因此都超过目标。一次移动就排除了所有包含这个右端的候选对。sum < target 时，同样可以排除 nums[lo] 与区间内其余元素组成的配对。
n 个元素共有 C(n, 2) 种不同位置的配对。暴力方法逐对检查；双指针每次排除当前端点对应的一批候选，最多 n − 1 次移动就能结束。播放器的候选对计数器显示每次移动排除了多少配对。
去掉有序性，这个推理就不成立。当前左端可能不是最小值，右端也可能不是最大值；被排除的端点可能还能与区间内某个值组成答案。
双指针逐步演示
默认输入为 nums = [1, 4, 6, 8, 11, 15]，目标为 target = 14。
lo = 0、hi = 5，得到1 + 15 = 16。因为16 > 14，排除 15，令hi = 4。lo = 0、hi = 4，得到1 + 11 = 12。因为12 < 14，排除 1，令lo = 1。lo = 1、hi = 4，得到4 + 11 = 15。和过大，令hi = 3。lo = 1、hi = 3，得到4 + 8 = 12。和过小，令lo = 2。lo = 2、hi = 3，得到6 + 8 = 14。命中，返回下标[2, 3]。
六个元素共有 C(6, 2) = 15 个候选对，这次只检查了五个和。排除是按端点成批完成的，不需要逐对计算。
动画中，连接两端的括号显示当前和，并随指针靠近而缩小。排除的端点变淡，候选对计数器随之变化。命中的两个元素变绿。
时间与空间复杂度
| 情况 | 时间复杂度 |
|---|---|
| 最好：首次两端就匹配 | O(1) |
| 平均 | O(n) |
| 最坏：配对靠近中间或不存在 | O(n) |
额外空间为 O(1)，只保存两个下标。如果输入还未排序，预先排序通常需要 O(n log n) 时间。只为寻找目标和，可以考虑平均 O(n) 时间、O(n) 空间的哈希方法，无需排序。双指针适合已有序的数据，或本来就需要排序的任务。
边界情况
- 空数组或单元素数组：初始
lo < hi不成立，返回[-1, -1]。 - 答案在两端：
nums[0] + nums[n−1]已等于目标，检查一次，无需移动。 - 不存在答案：指针向内移动，直到相遇，返回
[-1, -1]。 - 重复值：相等的值也能配对，但必须来自不同下标。
- 多个答案：返回扫描中遇到的一组，不枚举全部答案，也不保证唯一性。
常见错误
- 直接使用未排序输入：端点不再代表极值，排除规则可能漏掉答案。播放器的未排序场景会跳过
1 + 8 = 9，返回[-1, -1]。应先排序，或使用哈希方法。 - 移动方向写反：和太大时应让
hi左移；让lo右移只会使和不减。和太小时则让lo右移。 - 使用
lo <= hi：指针相遇后会把同一个位置用两次，产生题目不允许的配对。严格的<保证下标不同。 - 忽略排序成本和原下标：若只需判断目标和是否存在，未排序数据可以使用哈希集合。若先排序再返回位置，还需区分排序后的下标与原数组下标。