双指针

查找与遍历

说明

从两端或同向移动指针以避免重复扫描；下例查找有序数组中的目标和。

分析

有序数组的左右端相加后，和太小就移动左指针，太大就移动右指针。每一步都排除不可能的配对，因此只需线性扫描。

在有序[1,2,4,7]中找9，首尾和8偏小。1与任何不超过7的数相加都达不到9，因此可安全排除1；换成2就得到9。这个排除证明依赖有序性，无序输入不能照搬。

查看图表代码

适用前提与边界

输入无序时必须先排序或改用哈希表，并注意是否还需要原始下标。 双指针求和要求升序输入且两下标不同；空或单元素输入找不到配对，整数相加须避免溢出。

示例输入与调用

i, j, ok := PairSum([]int{1, 2, 4, 7}, 9)
	fmt.Println(i, j, ok)

运行输出

1 3 true

完整 Go 示例

package main

import "fmt"

func PairSum(a []int, target int) (int, int, bool) {
	i, j := 0, len(a)-1
	for i < j {
		s := a[i] + a[j]
		if s == target {
			return i, j, true
		}
		if s < target {
			i++
		} else {
			j--
		}
	}
	return 0, 0, false
}

func main() {
	i, j, ok := PairSum([]int{1, 2, 4, 7}, 9)
	fmt.Println(i, j, ok)
}