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

“Two Sum II - 输入数组已排序”问题是一个经典的编码挑战，测试您对数组和指针操作的理解。这也是展示优雅且高效的解决方案的绝佳机会。让我们深入研究这个问题并分解解决它的最佳方法。

LeetCode 上的问题链接

问题陈述

给定一个按非递减顺序排序的 1 索引整数数组，您的目标是找到两个数字，使其总和等于给定目标。您需要将这两个数字的索引作为数组 [index1, index2] 返回，其中 1

约束条件

• 数组编号按非递减顺序排序。
• 只有一个解决方案。
• 同一个元素不能使用两次。
• 输入数组长度范围为2到30,000。
• 数组中的值范围从 -1000 到 1000。

输入和输出示例

1. 输入： 数字 = [2,7,11,15]，目标 = 9
   
   输出： [1, 2]

2. 输入： 数字 = [2,3,4]，目标 = 6
   
   输出： [1, 3]

3. 输入： 数字 = [-1,0]，目标 = -1
   
   输出： [1, 2]

方法：两个指针

该问题的约束（排序数组和单个解决方案）使其成为两指针技术的完美候选者。原因如下：

• 效率：两个指针允许我们一次遍历数组（O(n) 时间复杂度）。
• 恒定空间：我们避免使用辅助数据结构，遵循问题对恒定额外空间的要求。

执行

下面是两指针方法的 JavaScript 实现：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    const length = nums.length;
    let rightPointer = length - 1;
    let leftPointer = 0;

    while (leftPointer < rightPointer) {
        if (nums[leftPointer] + nums[rightPointer] === target) {
            return [leftPointer + 1, rightPointer + 1];
        }
        if (nums[leftPointer] + nums[rightPointer] > target) {
            rightPointer--;
        } else {
            leftPointer++;
        }
    }
};

它是如何运作的

1. 初始化两个指针：

   • leftPointer 从数组的开头开始。
   • rightPointer 从数组末尾开始。

2. 迭代直到他们相遇：

   • 计算 leftPointer 和 rightPointer 处的元素之和。
   • 如果总和与目标匹配，则返回 1 索引位置。
   • 如果总和大于目标，则递减 rightPointer 以减少总和。
   • 如果总和小于目标，则增加 leftPointer 以增加总和。

3. 返回索引：

   • 一旦找到正确的对，循环就会终止并返回索引。

示例演练

让我们看一下第一个示例：

• 输入： 数字 = [2, 7, 11, 15]，目标 = 9
• 初始化：左指针 = 0，右指针 = 3

迭代步骤：

1. 计算数字[0] 数字[3] = 2 15 = 17。
   • 太大，将 right 指针减为 2。
2. 计算数字[0] 数字[2] = 2 11 = 13。
   • 仍然太大，将 right 指针递减到 1。
3. 计算数字[0] 数字[1] = 2 7 = 9。
   • 找到匹配项，返回 [1, 2]。

要点

• 1 索引调整： 问题指定基于 1 的索引，因此我们在返回之前将两个指针都加 1。
• 边缘情况：约束保证了单一解决方案，因此我们不需要处理空数组或多个匹配。
• 优化： 使用两指针方法确保我们满足 O(n) 时间复杂度和恒定空间要求。

结论

两指针方法通过利用输入数组的排序性质，优雅地解决了“Two Sum II - 输入数组已排序”问题。这是一种强大的技术，不仅可以确保效率，而且可以遵守空间限制，使其成为解决类似问题的首选方法。快乐编码！

以上是高效求解二和 II - 输入数组已排序的详细内容。更多信息请关注PHP中文网其他相关文章！