32-两数之和-II-输入有序数组
目录
32- 两数之和 II - 输入有序数组
给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。 以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。 你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。 你所设计的解决方案必须只使用常量级的额外空间。
方法一：双指针法
双指针法是处理有序数组中两数之和问题的经典方法，利用数组的有序性，通过两个指针从数组两端向中间移动来寻找符合条件的两个数。
function twoSum(numbers: number[], target: number): number[] {
let left = 0;
let right = numbers.length - 1;
while (left < right) {
const currentSum = numbers[left] + numbers[right];
if (currentSum === target) {
return [left + 1, right + 1];
} else if (currentSum < target) {
left++;
} else {
right--;
}
}
return [];
}复杂度分析
- 时间复杂度 ：(O(n))，其中 n 是数组的长度。因为两个指针最多遍历数组一次。
- 空间复杂度 ：(O(1))，只使用了常数级的额外空间来存储两个指针。
方法二：二分查找法
对于数组中的每个元素
numbers[i]
，我们可以使用二分查找在剩余的元素中查找是否存在
target - numbers[i]
。
function twoSum(numbers: number[], target: number): number[] {
for (let i = 0; i < numbers.length; i++) {
const complement = target - numbers[i];
let left = i + 1;
let right = numbers.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (numbers[mid] === complement) {
return [i + 1, mid + 1];
} else if (numbers[mid] < complement) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return [];
}复杂度分析
- 时间复杂度 ：(O(n log n))，对于数组中的每个元素，都需要进行一次二分查找，二分查找的时间复杂度是 (O(log n))，所以总的时间复杂度是 (O(n log n))。
- 空间复杂度 ：(O(1))，只使用了常数级的额外空间来存储二分查找所需的指针。
方法三：哈希表法
虽然本题要求使用常量级的额外空间，但哈希表法也是解决两数之和问题的常见思路，这里也给出实现以供参考。我们可以遍历数组，对于每个元素
numbers[i]
，检查
target - numbers[i]
是否在哈希表中，如果存在则返回对应的下标，否则将当前元素及其下标存入哈希表。
function twoSum(numbers: number[], target: number): number[] {
const hashMap = new Map<number, number>();
for (let i = 0; i < numbers.length; i++) {
const complement = target - numbers[i];
if (hashMap.has(complement)) {
return [hashMap.get(complement)! + 1, i + 1];
}
hashMap.set(numbers[i], i);
}
return [];
}复杂度分析
- 时间复杂度 ：(O(n))，只需要遍历数组一次，每次查找哈希表的时间复杂度是 (O(1))。
- 空间复杂度 ：(O(n))，主要用于存储哈希表，最坏情况下需要存储数组中的所有元素。
你可以使用以下方式测试这些函数：
const numbers = [2, 7, 11, 15];
const target = 9;
console.log(twoSum(numbers, target));综上所述，双指针法是本题的最优解法，时间复杂度和空间复杂度都较为优秀。