LeetCode经典算法题“两数之和 II - 输入有序数组”考察对数组和指针操作的理解，本文将深入探讨高效解法。
问题描述
给定一个已按升序排序的整数数组，找到两个数使得它们的和等于目标值。返回这两个数的索引 (1-based index)。
约束条件
- 数组已排序
- 只有一个解
- 不能重复使用同一个元素
- 数组长度 2 ≤ n ≤ 30000
- 数组元素 -1000 ≤ nums[i] ≤ 1000
示例
-
输入: numbers = [2,7,11,15], target = 9
输出: [1,2] -
输入: numbers = [2,3,4], target = 6
输出: [1,3] -
输入: numbers = [-1,0], target = -1
输出: [1,2]
解法：双指针法
由于数组已排序，双指针法是解决此问题的最佳方案，它具有O(n)时间复杂度和O(1)空间复杂度。
算法步骤
-
初始化指针:
leftPointer指向数组首元素，rightPointer指向数组尾元素。 -
迭代: 循环执行以下步骤直到
leftPointer和rightPointer相遇：- 计算
numbers[leftPointer] + numbers[rightPointer]的和。 - 若和等于目标值，则返回
[leftPointer + 1, rightPointer + 1](因为索引是1-based)。 - 若和大于目标值，则
rightPointer左移，减少和。 - 若和小于目标值，则
leftPointer右移，增加和。
- 计算
JavaScript 代码实现
/**
* @param {number[]} numbers
* @param {number} target
* @return {number[]}
*/
var twoSum = function(numbers, target) {
let left = 0;
let right = numbers.length - 1;
while (left < right) {
const sum = numbers[left] + numbers[right];
if (sum === target) {
return [left + 1, right + 1];
} else if (sum > target) {
right--;
} else {
left++;
}
}
};
算法分析
- 时间复杂度: O(n)，因为最多遍历数组一次。
- 空间复杂度: O(1)，因为只使用了常数个额外变量。
总结
双指针法巧妙地利用了数组已排序的特性，高效地解决了“两数之和 II - 输入有序数组”问题。 该方法简洁易懂，且时间和空间效率都非常高，是解决此类问题的最佳实践。
