给一个数组，找出其中和为n的两个元素

发表于 更新于 分类于
给一个数组，找出其中和为n的两个元素

题目如下

  • 给一个数组，找出其中和为n的两个元素

思路如下

  1. 嵌套循环，找到一个数，然后去遍历下一个数，求和，判断。此时的时间复杂度为O(n^2)
  2. 双指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
/**
 * @description 两数之和
 * @author sola-grj
 * 凡有序，必二分（思想）
 * 优化嵌套循环，可以考虑双指针
 */

/**
 * 寻找和为 n 的两个数（嵌套循环）
 * @param arr arr
 * @param n n
 */
export function findTwoNumbers1(arr: number[],n:number): number[] {
  const res: number[] = [];
  
  const length = arr.length
  if(length === 0) return res;
  
  for(let i = 0;i < length - 1;i++){
    const n1 = arr[i]
    let flag = false // 判断是否得到了结果
    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 的两个数（双指针）
 * @param arr arr
 * @param n n
 */
export function findTowNumbers2(arr: number[], n: number): number[] {
  const res: number[] = []
  
  const length = arr.length
  if(length === 0) return res
  
  let i = 0; // 头指针
  let j = length - 1 // 尾指针
  
  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))

console.time("findTowNumbers1");
for (let i = 0; i < 100 * 10000; i++) {
    findTowNumbers1(arr, 15);
}
console.timeEnd("findTowNumbers1"); // 730ms

console.time("findTowNumbers2");
for (let i = 0; i < 100 * 10000; i++) {
    findTowNumbers2(arr, 15);
}
console.timeEnd("findTowNumbers2"); // 102

单元测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * @description 两数之和 test
 * @author sola-grj
 */

import { findTowNumbers1, findTowNumbers2 } from './two-numbers-sum'

describe('两数之和', () => {
    it('正常情况', () => {
        const arr = [1, 2, 4, 7, 11, 15]
        const res = findTowNumbers2(arr, 15)
        expect(res).toEqual([4, 11])
    })

    it('空数组', () => {
        const res = findTowNumbers2([], 100)
        expect(res).toEqual([])
    })

    it('找不到结果', () => {
        const arr = [1, 2, 4, 7, 11, 15]
        const n = 100
        const res = findTowNumbers2(arr, n)
        expect(res).toEqual([])
    })
})