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

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

相似题目：
LeetCode 1. 两数之和

给你一个下标从 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
仅存在一个有效答案

蛮力法

内外联动双指针（外部指针决定范围，内部指针在外部指针决定的范围上操作），超时了，没有利用数据有序的特点

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:

        slow, length = 0, len(numbers)

        while slow < length:
            fast = slow + 1
            while fast < length:
                if numbers[slow] + numbers[fast] == target:
                    return [slow + 1, fast + 1]
                fast += 1
            slow += 1
1
2
3
4
5
6
7
8
9
10
11
12

哈希表
利用空间换时间，不合题意，也没有利用数字有序特点
…

二分查找
内循环利用数字有序特点降低时间复杂度

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:

        slow, length = 0, len(numbers)
        while slow < length:
            try:
                i = numbers[slow + 1 : length].index(target - numbers[slow])
            except ValueError:
                ...
            else:
                return [slow + 1, i + 1]
            slow += 1
1
2
3
4
5
6
7
8
9
10
11
12

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        n = len(numbers)
        for i in range(n):
            low, high = i + 1, n - 1
            while low <= high:
                mid = (low + high) // 2
                if numbers[mid] == target - numbers[i]:
                    return [i + 1, mid + 1]
                elif numbers[mid] > target - numbers[i]:
                    high = mid - 1
                else:
                    low = mid + 1
        
        return [-1, -1]

# 作者：力扣官方题解
# 链接：https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/solutions/337156/liang-shu-zhi-he-ii-shu-ru-you-xu-shu-zu-by-leet-2/
# 来源：力扣（LeetCode）
# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

左右逼近双指针（一个指针从左到右，一个指针从右到左，两个指针共同逼近正确答案）

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        low, high = 0, len(numbers) - 1
        while low < high:
            total = numbers[low] + numbers[high]
            if total == target:
                return [low + 1, high + 1]
            elif total < target:
                low += 1
            else:
                high -= 1

        return [-1, -1]

# 作者：力扣官方题解
# 链接：https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/solutions/337156/liang-shu-zhi-he-ii-shu-ru-you-xu-shu-zu-by-leet-2/
# 来源：力扣（LeetCode）
# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18