167.两数之和 II - 输入有序数组

【LetMeFly】167.两数之和 II - 输入有序数组

力扣题目链接：https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/

给你一个下标从 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] 。

 

提示：

• 2 <= numbers.length <= 3 * 104
• -1000 <= numbers[i] <= 1000
• numbers 按 非递减顺序 排列
• -1000 <= target <= 1000
• 仅存在一个有效答案

方法0.0：暴力

直接两重循环遍历数组，看能否找到两个数之和正好等于target。

• 时间复杂度$O(n^2)$，其中$n$是数组长度
• 空间复杂度$O(1)$

数组长度最大为$3\times 10^4$，$O(n^2)$运算量要接近$10^9$，不知道能不能通过，因此命名为方法0

方法0.1：哈希

预处理用哈希表记录出现过哪些元素（以及出现次数(防止$a+a=2a$重复计算)）

遍历一遍数组，看是否存在$target-当前元素$

• 时间复杂度$O(n)$，其中$n$是数组长度
• 空间复杂度$O(n)$

虽然能通过，但是不满足题目要求“使用常数的额外空间”

方法一：二分

数组是非递减的。因此我们可以遍历一遍原数组，在寻找$target - 当前元素$时，使用二分查找，看是否存在即可。

• 时间复杂度$O(n\log n)$，其中$n$是数组长度
• 空间复杂度$O(1)$

AC代码

C++

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int n = numbers.size();
        for (int i = 0; i < n; i++) {
            int finding = target - numbers[i];
            vector<int>::iterator it = lower_bound(numbers.begin() + i + 1, numbers.end(), finding);
            if (it == numbers.end() || *it != finding)
                continue;
            return {i + 1, (int)(it - numbers.begin() + 1)};
        }
        return {};  // Fake Return
    }
};

# from typing import List
# from bisect import bisect_left

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        n = len(numbers)
        for i in range(n):
            finding = target - numbers[i]
            loc = bisect_left(numbers, finding, i + 1)
            if loc < n and numbers[loc] == finding:
                return [i + 1, loc + 1]
        return []  # Fake Return

方法二：双指针

数组是非递减的。因此我们可以使用两个“指针”，初始位置分别为第一个元素和最后一个元素。

当两指针不重合时：

• 如果两元素之和正好等于target，那么我们就找到了答案，直接返回。
• 如果两元素之和小于target，那么左指针右移（越往右数越大）
• 如果两元素之和大于target，那么右指针左移（越往左数越小）

这样，每个元素最多被遍历一遍。

• 时间复杂度$O(n)$，其中$n$是数组长度
• 空间复杂度$O(1)$

AC代码

C++

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int l = 0, r = numbers.size() - 1;
        while (l < r) {
            int s = numbers[l] + numbers[r];
            if (s == target)
                return {l + 1, r + 1};
            else if (s < target)
                l++;
            else
                r--;
        }
        return {};  // Fake Return
    }
};

# from typing import List

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        l, r = 0, len(numbers) - 1
        while l < r:
            s = numbers[l] + numbers[r]
            if s == target:
                return [l + 1, r + 1]
            elif s < target:
                l += 1
            else:
                r -= 1
        return []  # Fake Return

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/126155983