剑指41-和为S的连续正整数序列

滑窗算法：

定义两个指针，用一个temp记录当前和，

temp<sum则右指针右移，temp>sum则左指针右移，temp=sum则push_back所有左指针到右指针元素

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int>> res;
        int l=1, r=1;
        int temp=0;
        while(l<=sum/2)
        {
            if(temp<sum){
                temp+=r;
                r++;
            }
            else if(temp>sum)
            {
                temp-=l;
                l++;
            }
            else
            {
                vector<int> t;
                for(int i=l;i<r;i++)
                {
                    t.push_back(i);
                }
                res.push_back(t);
                t.clear();
                temp-=l;  //左指针右移
                l++;
            }
        }

        return res;
    }
};

前缀和：

用两个循环，起点相同，

相当于两个指针，快指针右移，同时计算总和，temp记录

当temp>sum时，快指针回溯到慢指针，同时temp归0，重新进行上一步

链接：https://www.nowcoder.com/questionTerminal/c451a3fd84b64cb19485dad758a55ebe?answerType=1&f=discussion
来源：牛客网

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int>> ret;
        int tmp = 0;
        for (int i=1; i<=sum/2; ++i) {
            for (int j=i; j<sum; ++j) {
                tmp += j;
                if (sum == tmp) {
                    vector<int> ans;
                    for (int k=i; k<=j; ++k) ans.push_back(k);
                    ret.push_back(ans);
                }
                else if (tmp > sum) {
                    // 提前剪枝
                    tmp = 0;
                    break;
                }
            }
        }
        return ret;
    }
};