57.md

和为S的两个数字

题目

输入一个递增排序的数组array和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，返回任意一组即可，如果无法找出这样的数字，返回一个空数组即可

数据范围:

• 0<=len(array)<=105
• 1<=array[i]<=106

示例

• 输入：[1,2,4,7,11,15],15

• 返回值：[4,11]

• 说明：返回[4,11]或者[11,4]都是可以的

• 输入：[1,5,11],10

• 返回值：[]

• 说明：不存在，返回空数组

• 输入：[1,2,3,4],5

• 返回值：[1,4]

• 说明：返回[1,4],[4,1],[2,3],[3,2]都是可以的

思路

双指针

因为数组是有序的，所以可以用双指针，指向数组的首尾，具体步骤如下：

1. 初始化：指针i指向数组首， 指针j指向数组尾部
2. 如果arr[i] + arr[j] == sum , 说明是可能解
3. 否则如果arr[i] + arr[j] > sum, 说明和太大，所以--j
4. 否则如果arr[i] + arr[j] < sum, 说明和太小，所以++i

实现

func FindNumbersWithSum(nums []int, target int) []int {
	for i, j := 0, len(nums)-1; i < j; {
		if nums[i]+nums[j] > target {
			j--
		} else if nums[i]+nums[j] < target {
			i++
		} else {
			return []int{nums[i], nums[j]}
		}
	}
	return nil
}