第91题 给一个数组，找出其中和为n的两个元素（两数之和）

• 有一个递增数组[1,2,4,7,11,15]和一个n=15
• 数组中有两个数，和是n。即4 + 11 = 15
• 写一个函数，找出这两个数

思路分析

• 嵌套循环，找到一个数，然后去遍历下一个数，求和判断，时间复杂度是 O(n^2) 基本不可用
• 双指针方式，时间复杂度降低到O(n)
  • 定义i指向头
  • 定义j指向尾
  • 求arr[i] + arr[j]的和，如果大于n，则j向前移动j--，如果小于n，则i向后移动i++
• 优化嵌套循环，可以考虑双指针

寻找和为 n 的两个数（嵌套循环）

    /**
     * 寻找和为 n 的两个数（嵌套循环）
     * @param arr arr：number[]
     * @param n n：number
     */
    function findTowNumbers1(arr, n) {
      const res = []
    
      const length = arr.length
      if (length === 0) return res
    
      // 时间复杂度 O(n^2)
      for (let i = 0; i < length - 1; i++) {
        const n1 = arr[i]
        let flag = false // 是否得到了结果(两个数加起来等于n)
    
        // j从i + 1开始，获取第二个数n2
        for (let j = i + 1; j < length; j++) {
          const n2 = arr[j]
    
          if (n1 + n2 === n) {
            res.push(n1)
            res.push(n2)
            flag = true
            break // 调出循环
          }
        }
    
        // 调出循环
        if (flag) break
      }
    
      return res
    }

查找和为 n 的两个数（双指针）

随便找两个数，如果和大于n的话，则需要向前寻找，如果小于n的话，则需要向后寻找 -- 二分的思想

    /**
     * 查找和为 n 的两个数（双指针）
     * @param arr arr:number[]
     * @param n n:number
     */
    function findTowNumbers2(arr, n) {
      const res = []
    
      const length = arr.length
      if (length === 0) return res
    
      // ![](https://s.poetries.work/uploads/2023/01/28cd379998c81e43.png)
      let i = 0 // 定义i指向头
      let j = length - 1 // 定义j指向尾
      // 求arr[i] + arr[j]的和，如果大于n，则j向前移动j--，如果小于n，则i向后移动i++
    
      // 时间复杂度 O(n)
      while (i < j) {
        const n1 = arr[i]
        const n2 = arr[j]
        const sum = n1 + n2
    
        if (sum > n) { //sum 大于 n ，则 j 要向前移动
          j--
        } else if (sum < n) { // sum 小于 n ，则 i 要向后移动
          i++
        } else {
          // 相等
          res.push(n1)
          res.push(n2)
          break
        }
      }
    
      return res
    }

    // 功能测试
    const arr = [1, 2,1, 2,1, 2,1, 2,1, 2,1, 2,1, 2,1, 2,1, 2,1, 2,1, 2,1, 2,1, 2,1, 2, 4, 7, 11, 15]
    console.info(findTowNumbers2(arr, 15))

    // 性能测试
    
    // 寻找和为 n 的两个数（嵌套循环）
    console.time('findTowNumbers1')
    for (let i = 0; i < 100 * 10000; i++) {
        findTowNumbers1(arr, 15)
    }
    console.timeEnd('findTowNumbers1') // 730ms
    
    // 查找和为 n 的两个数（双指针）
    console.time('findTowNumbers2')
    for (let i = 0; i < 100 * 10000; i++) {
        findTowNumbers2(arr, 15)
    }
    console.timeEnd('findTowNumbers2') // 102ms
    
    // 结论：双指针性能优于嵌套循环方式