给一列已经排好序的数，问是否存在其中两个数之和等于给定的target，保证有且仅有一个解
试了两种方法，速度差不多
方法一：左右两个指针分别从首尾开始扫，如果相加小于target则左边指针右移，否则右边指针左移
1 #167
2 #Runtime: 237 ms
3 #Memory Usage: 14.3 MB
4
5 class Solution(object):
6 def twoSum(self, numbers, target):
7 """
8 :type numbers: List[int]
9 :type target: int
10 :rtype: List[int]
11 """
12 l = 0
13 r = len(numbers) - 1
14 while l < r:
15 if numbers[l] + numbers[r] == target:
16 return [l + 1, r + 1]
17 if numbers[l] + numbers[r] > target:
18 r -= 1
19 else:
20 l += 1
方法二：左边指针从第一个数开始向右扫，然后二分查找右边是否存在一个数与当前左边指针的数相加为target
1 #167
2 #Runtime: 243 ms
3 #Memory Usage: 14.9 MB
4
5 class Solution(object):
6 def twoSum(self, numbers, target):
7 """
8 :type numbers: List[int]
9 :type target: int
10 :rtype: List[int]
11 """
12 for i in range(0, len(numbers) - 1):
13 l = i + 1
14 r = len(numbers) - 1
15 while l <= r:
16 mid = int((l + r) / 2)
17 #print(mid)
18 if numbers[i] + numbers[mid] == target:
19 return([i + 1, mid + 1])
20 if numbers[i] + numbers[mid] < target:
21 l = mid + 1
22 else:
23 r = mid - 1