题目描述

输入一个正数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]]

算法1

(双指针)

1. 当s < sum　的时候，只是不断的将j指针右移。
2. 跳出while()循环的时候，只有２种情况，s == sum和s > sum。如果是s = sum，就记录答案。最后因为i指针要右移，所以s -= i。
3. 如果s > sum，那么直接i指针右移，也要 s -= i。所以一开始 s -= i 不能放在if{}中。
4. 一定要加　j > i，因为题目要求的是输出一个序列，而不是一个单个的数，不加的话会输出15。

时间复杂度

$O(n)$

C++ 代码

class Solution {
public:
    vector<vector<int> > findContinuousSequence(int sum) {
        vector<vector<int>> res;
        vector<int> path;
        for(int i = 1, j = 1, s = 1; i <= sum; i ++)
        {
            while(s < sum) j ++, s += j;

            // **1
            if(s == sum && j > i)
            {
                for(int k = i; k <= j; k ++) path.push_back(k);
                res.push_back(path);
                path.clear();
            }
            // **2
            s -= i;                                     
        }

        return res;
    }
};