【数据结构与算法】(10)：查找两数之和

给出一个数组，找出其中和为 n 的两个元素，本文就使用暴力嵌套循环和二分双指针的思路来实现这个算法。

一、问题描述

有一个 递增 的数组，找出和为 n 的 两个数，以数组的形式返回这两个数。

示例 1：

• 输入：[1,2,3,5,7,11,17] , n=16
• 输出：[5,11]

示例 2

• 输入：[23,55,78,100] , n=120
• 输出：[]

二、代码演示

1. 查找两数之和 嵌套循环

function findTwoNumbers1(arr: number[], n:number): number[] {
  let res: number[] = []

  const len = arr.length
  if (len === 0) return res

  for (let i = 0; i < len -1; i++) {
    let flag = false
    let x = arr[i]

    for (let j = i + 1; j < len; j++) {
      let y = arr[j]
      if (y + x === n) {
        res = [x, y]
        flag = true
        break
      }
    }
    if (flag) break
  }
  return res
}

2. 查找两数之和 双指针

function findTwoNumbers2(arr: number[], n:number): number[] {
  let res: number[] = []
  const len = arr.length
  if (len===0) return res

  let i = 0
  let j = len - 1

  while (i < j) {
    let n1 = arr[i]
    let n2 = arr[j]
    let 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
}

三、性能测试

在 0-1000 的 递增数组 中查找和为 15 的两个数，分别用 嵌套循环 和 双指针 方法来执行 100万次。

let arr3 = []
for (let i = 0; i < 1000; i++) {
  arr3.push(i)
}

console.time('findTwoNumbers1')
for (let i = 0; i < 100 * 10000; i++) {
  findTwoNumbers1(arr3, 15)
}
console.timeEnd('findTwoNumbers1')

console.time('findTwoNumbers2')
for (let i = 0; i < 100 * 10000; i++) {
  findTwoNumbers2(arr3, 15)
}
console.timeEnd('findTwoNumbers2')

运行


findTwoNumbers1 run time： 0

---

findTwoNumbers2 run time： 0

---

通过运行得知 嵌套循环 的方法远不如 双指针 的方法的执行效率。

四、算法复杂度

方法	时间复杂度
嵌套循环	O(n^2)
双指针	O(n)

---

《数据结构与算法》系列

1. 什么是算法复杂度
2. 堆(heap)、栈(stack)、队列(queue)
3. 把一个数组旋转k步
4. 判断字符串是否括号匹配
5. 数组、栈、链表、队列结构与对比
6. 用两个栈实现一个队列
7. 反转单向链表
8. 用链表实现队列
9. 二分查找
10. 查找两数之和
11. 求斐波那契数列的第n个值

---

欢迎访问：天问博客

本文作者： Tiven
发布时间： 2023-07-18
最后更新： 2023-07-21
本文标题： 【数据结构与算法】(10)：查找两数之和
本文链接： https://www.tiven.cn/p/4d88c947/
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明出处！