剑指offer 64- 和为S的连续正数序列

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

分析：
双指针算法
时间复杂度(抛去输出答案的时间)
设置两个指针i和j，分别指向连续正数序列的起始和终止

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

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

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

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/2;i++) {
            while(s<sum) s+=++j;
            if(s==sum && j>i) {
                for(int k=i;k<=j;k++) path.push_back(k);
                res.push_back(path);
                path.clear();
            }
            s-=i;
        }
        return res;
        
        /*vector<vector<int>> res;
        vector<int> path;
        for(int i = 1, j = 2; j < sum && i < j; ) {
            int ans = (i + j) * (j - i + 1) / 2;
            if ( ans == sum){//如果相同就加入。
                int k = i;
                while(k <= j)
                    path.push_back(k++);
                res.push_back(path);
                path.clear();
                i ++, j ++;//两个指针同时往后移。
            }
            else if ( ans < sum) {//如果比较小，j就往后移动。
                j ++;
            }
            else 
                i ++;//如果比较大，i往后移动
        }
        return res;*/

    }
};