题目

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

难度简单629 收藏分享切换为英文接收动态反馈

给定一个已按照**非递减顺序排列 **的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。

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

1. 踉踉跄跄调出来的二分解法

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:  
        for k,v in enumerate(numbers):
            new = numbers[0:k] + numbers[k+1:]  # 剔除元素本身，构造除本元素外的list
            l, r = 0, len(new) - 1
            while l < r:                
                mid = (l + r + 1) // 2
                if new[mid] <= target - v:
                    l = mid
                else:
                    r = mid - 1
            if new[l] + v == target: # 考虑到从numbers中剔除的数据可能是目标之前也可能在目标之后
                if l >= k:
                    return k+1, l + 2
                else:
                    return k+1, l + 1

看了官方题解后，发现自己想多了？？？下面的代码也能AC。。。

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:  
        for k,v in enumerate(numbers):            
            l, r = 0, len(numbers) - 1
            while l < r:                
                mid = (l + r + 1) // 2
                if numbers[mid] <= target - v:
                    l = mid
                else:
                    r = mid - 1
            if numbers[l] + v == target: 
                return k+1, l + 1
        return [-1, -1]

2. 官方优美的二分解法题解链接

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]

3. 哈？双指针？什么黑科技

看了题解的文字描述写出的双指针

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

官方题解的双指针：

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]

初始时两个指针分别指向第一个元素位置和最后一个元素的位置。每次计算两个指针指向的两个元素之和，并和目标值比较。如果两个元素之和等于目标值，则发现了唯一解。如果两个元素之和小于目标值，则将左侧指针右移一位。如果两个元素之和大于目标值，则将右侧指针左移一位。移动指针之后，重复上述操作，直到找到答案。

使用双指针的实质是缩小查找范围。那么会不会把可能的解过滤掉？答案是不会。假设 $numbers[i]+numbers[j]=target$ 是唯一解，其中 $0≤i<j≤numbers.length−1$ 。初始时两个指针分别指向下标 $0$ 和下标 $numbers.length−1$ ，左指针指向的下标小于或等于 $i$ ，右指针指向的下标大于或等于 $j$ 。除非初始时左指针和右指针已经位于下标 $i$ 和 $j$ ，否则一定是左指针先到达下标 $i$ 的位置或者右指针先到达下标 $j$ 的位置。