1. 题目描述

输入一个递增排序的数组和一个数字 s,在数组中查找两个数,使得它们的和正好是 s。如果有多对数字的和等于 s,输出任意一对即可。

2. 解题思路

如果这个数组不是递增的,就得用哈希表来解决,空间复杂度是 O(N)。

但是题目条件是“递增数组”,因此可以使用“双指针”的思路来实现:即一个指针指向开头,另一个指向结尾。

比较指针对应的 2 个元素的和与给定数组 s:

  • 元素和 > s: 后指针向前移动
  • 元素和 < s: 前指针向后移动
  • 元素和 = s: 返回指针对应的 2 个元素

3. 代码实现

/**
 *
 * @param {Array} data
 * @param {Number} sum
 */
function findNumsWithSum(data, sum) {
  if (!Array.isArray(data) || data.length <= 1) {
    return [null, null];
  }
  let i = 0,
    j = data.length - 1;
  while (i < j) {
    let now = data[i] + data[j];
    if (now === sum) {
      return [data[i], data[j]];
    } else if (now > sum) {
      --j;
    } else {
      ++i;
    }
  }

  return [null, null];
}

/**
 * 以下是测试代码
 */

// 输出:[ 4, 11 ]
console.log(findNumsWithSum([1, 2, 4, 7, 11, 15], 15));
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