--- created: '2019-06-13T05:38:27.295Z' modified: '2019-08-03T18:17:05.139Z' ---

167. Two Sum II - Input array is sorted

History

19/6/13

乍一看，稍微用下面的思路即可：

... for n in nums: binary_search(target - n) ...

但这样要 $O(n(\log n))$ 的时间复杂度

---

看了下 discussion ，可以用 two-potiner 实现 $O(n)$ 的时间复杂度

---

整个解空间由 $<a,b>$ (a,b 是数组的 index 范围）的有序对组成，共有 $n\times n$ 个

题目已经说明，一定有解。

two-potiner 相对于穷举而言，不过是利用额外性质（这里是有序）更快、更多地抛弃掉不可能的空间 —— 二分搜索也是这样的原理

画个 $n\times n$ 的二维表格会更加形象化地明白；纸上容易画出来，这里不容易

---

得到：

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