找出一个数组中和为n的两个数
实现目标
- 一个递增的数组 [1,2,4,7,11,15] 和一个 n=15
- 数组中有两个数,和为 n。即 4+11=15
- 实现函数找出这两个数
实现思路
嵌套循环方式
- 找出一个数,然后遍历下一个数,求和,判断
- 时间复杂度是 O(n^2),不可用了
双指针思路
- 随便找两个数
- 如果和大于 n,则需要向前寻找 - 利用递增(有序)的特性
- 如果和小于 n, 则需要向后查找 - 二分法
- 时间复杂度降低到 O(n),具体思路
- 定义 i 指向头,j 指向尾,求 arr[i]+arr[j]
- 如果大于 n,则 j 需要向前移动
- 如果小于 n,则 i 需要向后移动
代码实现
性能测试
console.time('twoNumberSum1')
for(let i=0;i<100*10000;i++){
twoNumberSum1(arr, n)
}
console.timeEnd('twoNumberSum1') // 204.293ms
console.time('twoNumberSum2')
for(let i=0;i<100*10000;i++){
twoNumberSum2(arr, n)
}
console.timeEnd('twoNumberSum2') // 49.095ms