1. 题目描述

输入一个正数 s，打印出所有和为 s 的连续正数序列（至少含有两个数）。例如输入 15，由于 1 ＋ 2 ＋ 3 ＋ 4 ＋ 5 ＝ 4 ＋ 5 ＋ 6 ＝ 7 ＋ 8 ＝ 15，所以结果打印出 3 个连续序列 1 ～ 5、4 ～ 6 和 7 ～ 8。

2. 思路分析

和前面题目很相似，这里也是“双指针”的思路。不同的地方有 2 个点：

  • 指针是从第 0 个和第 1 个位置开始的（下面称为 a 和 b）
  • 这里要计算指针范围内的所有元素和（题目要求是“连续序列”）

每次移动 a、b 之前，都要计算一下当前[a,b]范围内的所有元素和。如果等于 s，打印并且 b 右移；如果小于 s，b 右移；如果大于 s，a 右移。

至于为什么相等的时候 b 右移而不是 a 右移？因为 a 右移会漏掉情况，而且指针可能重叠。比如对于数组 [1, 2, 2]，给定 s 是 3。

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * 打印指定数组的起始下标内的所有元素
 *
 * @param {Array} data 打印数组
 * @param {Array} seq [start, end] 数组打印元素的起始下标
 */
function print(data, seq) {
    const [start, end] = seq
    for (let i = start; i <= end; ++i) {
        process.stdout.write(data[i] + ', ')
    }
    process.stdout.write('\n')
}

/**
 * 打印出递增数组中，所有和为s的元素
 *
 * @param {Array} data 递增数组
 * @param {Number} sum 和
 */
function findSequenceWithSum(data, sum) {
    let small = 0,
        big = 1,
        cur = data[small] + data[big]
    const middle = (data.length + 1) >> 1
    while (small < middle) {
        if (cur <= sum) {
            cur === sum && print(data, [small, big])
            ++big
            cur += data[big]
        } else {
            cur -= data[small]
            ++small
        }
    }
}

/**
 * 测试代码
 */

// 输出：
// 2, 3, 4,
// 4, 5,
findSequenceWithSum([1, 2, 3, 4, 5, 6, 7, 8], 9)