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

🟠   🔖  数组 双指针 二分查找  🔗 力扣 LeetCode

题目

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order , find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 < numbers.length.

Return the indices of the two numbers,index1 and index2 _, added by one as an integer array _[index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

Example 1:

Input: numbers = [ 2 , 7 ,11,15], target = 9

Output: [1,2]

Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

Example 2:

Input: numbers = [ 2 ,3, 4 ], target = 6

Output: [1,3]

Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].

Example 3:

Input: numbers = [ -1 , 0 ], target = -1

Output: [1,2]

Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].

Constraints:

• 2 <= numbers.length <= 3 * 10^4
• -1000 <= numbers[i] <= 1000
• numbers is sorted in non-decreasing order.
• -1000 <= target <= 1000
• The tests are generated such that there is exactly one solution.

题目大意

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

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

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

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

解题思路

思路一：双指针（对撞指针）

1. 数组有序性：题目给定的数组是有序的，因此可以利用数组的有序性来减少遍历次数。
2. 双指针的思想：
   • 初始化两个指针，一个从数组的起始位置 i = 0，一个从数组的末尾位置 j = numbers.length - 1。
   • 然后将这两个指针所指的元素相加，比较其和与目标 target 的关系：
     • 如果两数之和正好等于 target，则返回这两个指针的索引值（注意题目要求返回的是 1-based 索引，所以需要加 1）。
     • 如果和小于 target，说明需要更大的数，左指针向右移动一位（i++）。
     • 如果和大于 target，说明需要更小的数，右指针向左移动一位（j--）。
3. 终止条件：指针相遇时退出循环。

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组的长度，由于只需要一次遍历整个数组（每个元素最多被遍历一次），所以时间复杂度为 O(n)。
• 空间复杂度：O(1)，除了几个额外的指针变量，没有使用其他额外的存储空间。

思路二：哈希表

这一解法不要求数组是有序的，可以处理任意无序数组。

• 遍历数组，同时用一个哈希表 obj 来记录已经遍历过的数字及其索引。
• 对于每个遍历到的数字 numbers[i]，计算 target - numbers[i] 的值，称之为 another。
• 然后检查 another 是否已经在哈希表中存在：
  • 如果存在，说明已经找到了一组符合条件的数字，返回它们的索引值。（注意题目要求返回的是 1-based 索引，所以需要加 1）。
  • 如果不存在，则将当前数字 numbers[i] 和它的索引 i 存入哈希表中。

哈希表查找时间复杂度为 O(1)，因此可以通过这种方法快速找到目标和。

复杂度分析

• 时间复杂度：O(n)，需要遍历一次数组，时间复杂度为 O(n)，在遍历的过程中，哈希表的查找和插入操作的时间复杂度都是 O(1)。
• 空间复杂度：O(n)，由于需要用哈希表来存储已经遍历过的数字及其索引，哈希表的空间复杂度为 O(n)。

代码

对撞指针

// 解法一 这一题可以利用数组有序的特性，使用对撞指针
/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (numbers, target) {
	let i = 0;
	let j = numbers.length - 1;
	while (i < j) {
		if (numbers[i] + numbers[j] === target) {
			return [i + 1, j + 1];
		} else if (numbers[i] + numbers[j] < target) {
			i++;
		} else {
			j--;
		}
	}
};

哈希表

// 解法二 不管数组是否有序，空间复杂度比上一种解法要多 O(n)
/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (numbers, target) {
	let obj = {};
	for (let i = 0; i < numbers.length; i++) {
		let another = target - numbers[i];
		if (another in obj) {
			return [obj[another] + 1, i + 1];
		}
		obj[numbers[i]] = i;
	}
};

相关题目

题号	标题	题解	标签	难度
1	两数之和	[✓]	数组 哈希表
653	两数之和 IV - 输入二叉搜索树		树 深度优先搜索 广度优先搜索 4+
1099	小于 K 的两数之和 🔒		数组 双指针 二分查找 1+