【数据结构与算法】(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')

<div> <button style='padding: 10px 20px; color: #00b1fb;' class='rotate-btn' onclick='run()'>运行</button> <br> <b>findTwoNumbers1 run time：</b> <span style='color: red;' class='box1-ms'>0</span> <hr> <b>findTwoNumbers2 run time：</b> <span style='color: red;' class='box2-ms'>0</span> <hr> </div> <script> // 查找两数之和 // 嵌套循环 O(n^2) function findTwoNumbers1(arr, n) { let res = []

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

}

// 查找两数之和 // 双指针 function findTwoNumbers2(arr, n) { let res = [] 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

}

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

let s1 = performance.now()
for (let i = 0; i < 100 * 10000; i++) {
  findTwoNumbers1(arr3, 15)
}
document.querySelector('.box1-ms').innerText = performance.now() - s1 + ' ms'

let s2 = performance.now()
for (let i = 0; i < 100 * 10000; i++) {
  findTwoNumbers2(arr3, 15)
}
document.querySelector('.box2-ms').innerText = performance.now() - s2 + ' ms'

} </script>

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

四、算法复杂度

《数据结构与算法》系列

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

欢迎访问：天问博客