题目描述

输入一个正数 S，打印出所有和为 S 的连续正数序列（至少含有两个数）。

例如输入 15，由于 1+2+3+4+5=4+5+6=7+8=15，所以结果打印出 3 个连续序列 1∼5、4∼6 和 7∼8。

样例

输入：15

输出：[[1,2,3,4,5],[4,5,6],[7,8]]

算法

(双指针算法) $O(n)$

最容易想到的是用两重循环去枚举和为 $S$ 的序列，时间复杂度是 $O(n^2)$
我们可以使用双指针算法进行优化，用两个指针 $i, j$ 指向当前正在枚举的序列的起点和终点

1. 当 $i \sim j$ 之间的和小于 $S$ 时， $j$ 指针往后移
2. 当 $i \sim j$ 之间的和等于 $S$ 时，记录当前序列，加入到答案中
3. 当 $i \sim j$ 之间的和大于 $S$ 时，$i$ 指针往后移

可以 $i$ 和 $j$ 是单调的，不会走回头路，且当 $i$ 往后移时 $j$ 不会往前移

时间复杂度

$i$ 和 $j$ 最终都从 $1$ 走到 $target$，时间复杂度为 $O(n)$

C++ 代码

class Solution {
public:
    vector<vector<int> > findContinuousSequence(int sum) {
        vector<vector<int>> res;

        for (int i = 1, j = 1, s = 1; i < sum; i ++ )
        {
            while (s < sum) j ++ , s += j;
            if (s == sum)
            {
                vector<int> line;
                for (int k = i; k <= j; k ++ ) line.push_back(k);
                res.push_back(line);
            }
            s -= i;
        }

        return res;
    }
};