高效求解二和 II - 输入数组已排序

LeetCode经典算法题“两数之和 II - 输入有序数组”考察对数组和指针操作的理解，本文将深入探讨高效解法。

问题描述

给定一个已按升序排序的整数数组，找到两个数使得它们的和等于目标值。返回这两个数的索引 (1-based index)。

约束条件

• 数组已排序
• 只有一个解
• 不能重复使用同一个元素
• 数组长度 2 ≤ n ≤ 30000
• 数组元素 -1000 ≤ nums[i] ≤ 1000

示例

1. 输入: numbers = [2,7,11,15], target = 9
   输出: [1,2]
2. 输入: numbers = [2,3,4], target = 6
   输出: [1,3]
3. 输入: numbers = [-1,0], target = -1
   输出: [1,2]

解法：双指针法

由于数组已排序，双指针法是解决此问题的最佳方案，它具有O(n)时间复杂度和O(1)空间复杂度。

算法步骤

1. 初始化指针: leftPointer 指向数组首元素，rightPointer 指向数组尾元素。
2. 迭代: 循环执行以下步骤直到 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 - 输入有序数组”问题。 该方法简洁易懂，且时间和空间效率都非常高，是解决此类问题的最佳实践。

以上就是高效求解二和 II - 输入数组已排序的详细内容，更多请关注php中文网其它相关文章！