1. 题目描述

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

2. 解题思路

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

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

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

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

3. 代码实现

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
/**
 *
 * @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))