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

发表于 更新于 分类于
这是文章开头，显示在主页面，详情请点击此处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        # 暴力枚举，太耗时。
        # for i in range(len(numbers)):
        #     y = target-numbers[i]
        #     for j in range(i+1,len(numbers)):
        #         if y == numbers[j]:
        #             return [i+1,j+1]
        # 二分法
        for i in range(len(numbers)):
            y = target-numbers[i]
            left = i+1
            right = len(numbers)-1
            while left<=right:
                half = (left+right)>>1
                if numbers[half]==y:
                    return [i+1,half+1]
                elif numbers[half]>y:
                    right = half-1
                else:
                    left = half+1