两数之和

题目

输入一个递增的数字数组，和一个数字 n 。求和等于 n 的两个数字。
例如输入 [1, 2, 4, 7, 11, 15] 和 15 ，返回两个数 [4, 11]

分析

注意题目的要点

• 递增，从小打大排序
• 只需要两个数字，而不是多个

常规思路

嵌套循环，找个一个数，然后再遍历剩余的数，求和，判断。

时间复杂度 O(n^2) ，基本不可用。

利用递增的特性

数组是递增的

• 随便找两个数
• 如果和大于 n ，则需要向前寻找
• 如果和小于 n ，则需要向后寻找 —— 二分法

双指针（指针就是索引，如数组的 index）

• i 指向头，j 指向尾， 求 i + j 的和
• 和如果大于 n ，则说明需要减少，则 j 向前移动（递增特性）
• 和如果小于 n ，则说明需要增加，则 i 向后移动（递增特性）

时间复杂度降低到 O(n)

答案

方案二，参考 two-numbers-sum.ts

划重点

• 有序数据，要善用二分法
• 优化嵌套循环，可以考虑“双指针”