给出一个数组，找出其中和为 n 的两个元素，本文就使用暴力嵌套循环和二分双指针的思路来实现这个算法。
一、问题描述
有一个 递增 的数组，找出和为 n 的 两个数，以数组的形式返回这两个数。
示例 1：
- 输入：
[1,2,3,5,7,11,17] , n=16
- 输出：
[5,11]
示例 2
- 输入：
[23,55,78,100] , n=120
- 输出：
[]
二、代码演示
- 查找两数之和 嵌套循环
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
}
- 查找两数之和 双指针
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')
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'
}
通过运行得知 嵌套循环 的方法远不如 双指针 的方法的执行效率。
四、算法复杂度
《数据结构与算法》系列
- 什么是算法复杂度
- 堆(heap)、栈(stack)、队列(queue)
- 把一个数组旋转k步
- 判断字符串是否括号匹配
- 数组、栈、链表、队列结构与对比
- 用两个栈实现一个队列
- 反转单向链表
- 用链表实现队列
- 二分查找
- 查找两数之和
- 求斐波那契数列的第n个值
欢迎访问：天问博客
