167. 两数之和 II - 输入有序数组

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列  ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

 

示例 1：

输入：numbers = [_2_,_7_,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

示例 2：

输入：numbers = [_2_,3,_4_], target = 6
输出：[1,3]
解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。

示例 3：

输入：numbers = [_-1_,_0_], target = -1
输出：[1,2]
解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

提示：

  • 2 <= numbers.length <= 3 * 104
  • -1000 <= numbers[i] <= 1000
  • numbers 按 非递减顺序 排列
  • -1000 <= target <= 1000
  • 仅存在一个有效答案

从左右两边出发，如果和比目标值小，那么左边 ++ ，如果比目标值大，那么右边 –，直到找到目标答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func twoSum(numbers []int, target int) []int {
	low, high := 0, len(numbers) - 1
	for low < high {
		sum := numbers[low] + numbers[high]
		if sum == target {
			return []int{low + 1, high + 1}
		} else if sum < target {
			low++
		} else {
			high--
		}
	}
	return []int{-1, -1}
}

按照普通 2sum 的方法，因为是有序的数组，原先普通遍历的方案可以改成 二分查找 target - num[i]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func twoSum(numbers []int, target int) []int {
	for i:=0; i<len(numbers); i++ {
		low, high := i+1, len(numbers)-1
		nextTar := target - numbers[i]
		for low <= high {
			mid := (high-low)/2 + low
			if numbers[mid] == nextTar {
				return []int{i+1, mid+1}
			} else if numbers[mid] > nextTar {
				high = mid-1
			} else {
				low = mid+1
			}
		}
	}
	  
	return []int{-1, -1}
}