题目

给你一个下标从 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
func twoSum(numbers []int, target int) []int {
	for i, m := 0, make(map[int]int, 0); i < len(numbers); i++ {
		if res, ok := m[target-numbers[i]]; ok {
			return []int{res + 1, i + 1}
		} else {
			m[numbers[i]] = i
		}
	}

	return []int{}
}

暴力解法

后来看到题目要求使用常量级的额外空间，所以直接暴力解法也是可以的：

1
2
3
4
5
6
7
8
9
10
11
12
13
func twoSum(numbers []int, target int) []int {
	for i, num := range numbers {
		for j := i + 1; j < len(numbers); j++ {
			if x := numbers[j] + num; x == target {
				return []int{i + 1, j + 1}
			} else if x > target {
				break
			}
		}
	}

	return []int{}
}

这里当 x > target 时直接跳出内层循环，因为数组是有序的，后面的元素一定会更大。并且由于数组是有序的，可以考虑在查找时使用二分查找来提高效率。

二分查找法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
func binarySearch(target int, numbers []int) int {
    left, right := 0, len(numbers)-1
	if target < numbers[left] || target > numbers[right] {
		return -1
	}

	for left <= right {
		mid := (left + right) / 2
		if numbers[mid] == target {
			return mid
		} else if numbers[mid] > target {
			right = mid - 1
		} else {
			left = mid + 1
		}
	}

	return -1
}

func twoSum(numbers []int, target int) []int {
	for i := 1; i < len(numbers); i++ {
		if j := binarySearch(target-numbers[i-1], numbers[i:]); j >= 0 {
			return []int{i, i + j + 1}
		}
	}

	return []int{}
}

这样时间复杂度为 O(nlogn)，空间复杂度为 O(1)。提交后耗时为 0ms，内存为 7.63MB。

双指针法

上面的方法，都是遍历数组的每一个数，根据每一个数和目标值的差值来查找另一个数。而由于数组是有序的，所以用二分查找优化了查找的时间复杂度。但其实有部分查找是重复的，如果考虑优化这部分重复，就要用空间换时间，记录每一个元素和目标值的差值。但是这样就会增加空间复杂度。如果要想同时降低时间复杂度和空间复杂度，就要从另一个角度考虑问题 缩减查找的范围：

  • 初始的搜索范围是 i := 0 到 j := len(numbers)-1，即整个数组。
  • 如果 numbers[i] + numbers[j] == target，则直接返回 i 和 j。
  • 如果 numbers[i] + numbers[j] < target，则说明 numbers[i] + numbers[j] 不够大，可以进一步压缩范围，即 i++。
  • 如果 numbers[i] + numbers[j] > target，则说明需要减小 numbers[i] + numbers[j]，可以进一步压缩范围，即 j--。

所以可以使用双指针法来实现，时间复杂度为 O(n)，空间复杂度为 O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
func twoSum(numbers []int, target int) []int {
	for i, j := 1, len(numbers); i < j; {
		if x := numbers[i-1] + numbers[j-1]; x == target {
			return []int{i, j}
		} else if x > target {
			j--
		} else {
			i++
		}
	}

	return []int{}
}