题目描述

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

(双指针) $O(n)$

1. 设置两个指针i和j，分别指向连续正数序列的起始和终止

2. 用s表示当前连续正数序列的和，即$s=i+(i+1)+…+j$

3. 以i递增的方式遍历整个序列(1到n)，代表查找以i开头的时候结尾j应该是多少。当$s < sum$说明j应该往后移动，当$s=sum$说明满足题意，当$s>sum$说明向后走即可。

4. 注意上述遍历过程中，$s=sum$的情况下不需要把j往前移动，原因是当进入下一个循环前$s-=i$，即(i+1)到j的和肯定小于sum。

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 && j > i)
            {
                vector<int> line;
                for (int k = i; k <= j; k ++ ) line.push_back(k);
                res.push_back(line);
            }
            s -= i;
        }
        return res;
    }
};

作者：yxc
链接：https://www.acwing.com/activity/content/code/content/25914/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。