LeetCode算法入门 — 输入有序数组-一一网

Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。

两数之和 II – 输入有序数组

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

示例 1：

输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
复制代码

示例 2：

输入：numbers = [2,3,4], target = 6
输出：[1,3]
解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。
复制代码

示例 3：

输入：numbers = [-1,0], target = -1
输出：[1,2]
解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
复制代码

思路分析

方法一

简单粗暴的双层循环，判断条件，然后返回下标。

方法二

因为数组是有序的，所以可以使用二分查找。
寻找两个数的和等于目标值，可以先固定一个数，然后找另一个数，另一个数就等于目标值减去第一个数。
依旧定义左边界、右边界以及中值，循环移动获取即可。

AC 代码

方法一

/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(numbers, target) {
    const len = numbers.length
    for(let i = 0; i < len; i++) {
        for(let j = i + 1; j < len; j++) {
            if(numbers[i] + numbers[j] === target) {
                return [i + 1, j + 1]
            }
        }
    }
};
复制代码

结果：

执行结果：通过
执行用时：548 ms, 在所有 JavaScript 提交中击败了5.06%的用户
内存消耗：42 MB, 在所有 JavaScript 提交中击败了44.43%的用户
通过测试用例：21 / 21

方法二

/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(numbers, target) {
    for (let i = 0; i < numbers.length; i++) {
        let low = i + 1
        let high = numbers.length - 1
        while (low <= high) {
            let mid = Math.floor((high - low) / 2) + low;
            if (numbers[mid] === target - numbers[i]) {
                return [i + 1, mid + 1];
            } else if (numbers[mid] > target - numbers[i]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
    }
};
复制代码