找出一个数组中和为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