刷题笔记(5):力扣-167.两数之和 II - 输入有序数组

本题来自 leetcode 题库第 167 题:167.两数之和 II - 输入有序数组。题目要求在有序数组中找和为指定值的两个数,难度简单。

题目描述

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

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

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

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

  • 示例 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 * \(10^4\)
    -1000 <= numbers[i] <= 1000
    numbers 按非递减顺序排列
    -1000 <= target <= 1000
    仅存在一个有效答案

题解

解法1 二分查找

由于题目输入的数组是有序数组,那么就可以固定一个加数,使用二分法查找另外一个加数。注意到一些细节可以降低复杂度,例如查找第二个加数只需要在第一个加数之后查找,便可做到不重不漏。二分查找时,若目标值小于待查找序列的第一个值或大于最后一个值,便可知道查找不到。

代码实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* @param {number[]} numbers
* @param {number} target
* @return {number[]}
*/
var twoSum = function (numbers, target) {
for (let i = 0; i < numbers.length; i++) {
const a = target - numbers[i]
let head = i + 1, tail = numbers.length - 1
let middle = Math.floor((head + tail) / 2)
while (head <= tail) {
if (numbers[middle] === a) return [i + 1, middle + 1]
if (a > numbers[middle]) head = middle + 1
else tail = middle - 1
middle = Math.floor((head + tail) / 2)
}
}
}

该方法时间复杂度为 \(O(n\log n)\),空间复杂度为 \(O(1)\)

解法2 双指针

该算法维护两个指针 i < j,依次从首尾向中间搜索。由于数组是正序的,若当前两个指针所指的数的和大于目标值,即 numbers[i] + numbers[j] > target,则令 j--;若 numbers[i] + numbers[j] < target,则令 i++。那么为何该方法是有效的呢,这涉及到压缩搜索空间的问题。简单描述如下:

考虑当 i = 0, j = numbers.length - 1 时。若此时两个数的和大于目标值,由于 numbers[i] 已经是数组中最小的值了,numbers[j] 加上 numbers[i] 的和仍然大于目标值,那么说明 numbers[j] 加上数组中的任何值都大于目标值,因此令 j--,直接排除掉 j = numbers.length 时所有情况。同理,若此时两个数的和小于目标值,由于 numbers[j] 是数组中最大值,而 numbers[i] 加上它仍然小于目标值,则说明 numbers[i] 加上数组中的其他任意值也一定小于目标值,因此令 i++,排除掉 i = 0 的所有情况。依次类推,直至寻找到正确的答案。(更详细的解释可参考一张图告诉你 O(n) 的双指针解法的本质原理(C++/Java)

具体的代码实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* @param {number[]} numbers
* @param {number} target
* @return {number[]}
*/
var twoSum = function (numbers, target) {
let i = 0, j = numbers.length - 1
while (i < j) {
const sum = numbers[i] + numbers[j]
if (sum === target) return [i + 1, j + 1]
if (sum < target) i++
else j--
}
}

该算法的时间复杂度为 \(O(n)\),空间复杂度为 \(O(1)\)

总结与思考

这道题虽然思路很简单,但二分查找写起来还是有些细节要注意。双指针无疑是一个既容易理解有高效简洁的算法,且不容易写错!