题解 | #和为S的连续正数序列#

先用暴力法解。
用一个二重循环遍历1～sum/2+1中的数。
外层循环控制该连续序列的起点，内层循环用于记录该序列以及该序列的和。
当序列和等于sum时，将当前序列加入结果集，退出内层循环。当序列和大于sum时，直接退出内层循环。
这样做时间复杂度在O(n^2)，空间复杂度为O(n)。

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int>> res;
        if(!sum){
            return res;
        }
        for(int i = 1;i < sum / 2 + 1;i++){
            int count = 0;
            vector<int> temp;
            for(int j = i;j < sum / 2 + 2;j++){
                count += j;
                temp.push_back(j);
                if(count == sum){
                    res.push_back(temp);
                    break;
                }
                if(count > sum){
                    break;
                }
            }
        }
        return res;
    }
};

更好的方法是用滑动窗口的方法来做。
用两个指针来标记窗口的边界，每次计算窗口内数字的和，当和大于sum时，窗口左边界右移，当和小于sum时，窗口右边界右移。
由于连续序列的定义要求最少要两个数字，所以终止条件为窗口的右边界超过sum/2+1。
这个算法最巧妙的地方在于计算窗口中的和时，不需要累加，而直接用等差数列求和公式即可。

时间复杂度为O(n)，空间复杂度为O(n)。

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int>> res;
        if(!sum){
            return res;
        }
        int left = 1;
        int right = 2;
        while(right < sum / 2 + 2){
            int count = (left + right) * (right - left + 1) / 2;
            if(count > sum){
                left++;
            }
            else if(count < sum){
                right++;
            }
            else{
                vector<int> temp;
                for(int i = left;i < right + 1;i++){
                    temp.push_back(i);
                }
                res.push_back(temp);
                right++;
            }
        }
        return res;
    }
};