給一列已經(jīng)排好序的數(shù)，問是否存在其中兩個數(shù)之和等于給定的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
方法二：左邊指針從第一個數(shù)開始向右掃，然后二分查找右邊是否存在一個數(shù)與當前左邊指針的數(shù)相加為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