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 代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* @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 - 输入数组已排序的详细内容，更多请关注php中文网其它相关文章！