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

题目难度：中等
题目考察：枚举，尺取
题目内容：输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序
题目分析
这是尺取的典型题目，但是还是要先考虑暴力做法，我们都知道等差数列求和可以用(a1+an)项数/2,而项数可以通过首项和尾项求出来，也就是说可以枚举首项和尾项来暴力求解，如图所示

很明显，这样做的复杂度是O(n^2)的
下面给出代码
*算法1（枚举）**

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int> >a;
        //记录所有满足的序列
        for(int i=1;i<sum;i++)
            //枚举首项
            for(int j=i+1;(i+j)*(j-i+1)/2<=sum;j++)
            {
                //枚举尾项
                if((i+j)*(j-i+1)/2==sum){
                    //序列和=sum则是一个满足的序列
                    vector<int>ans;
                    for(int k=i;k<=j;k++)
                        ans.push_back(k);
                    //记录满足的序列
                    a.push_back(ans);
                    //加到所有答案里
                }
            }
        return a;
    }
};

时间复杂度O(n^2)
空间复杂度O(n^2)
算法2（尺取）
尺取利用的就是单调性，看图

这时候还不是特别明确，单调性在哪呢，右端点向右和一直变大，左端点向右和一直变小，当和大于sum时右端点就没有必要再向右走了，这时让左端点向右走到和小于等于sum，这么做怎么保证答案没有遗漏呢，这是需要考虑的**

这也就保证了没有答案被遗漏
下面给出代码

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int> >a;
        for(int i=1,j=1,now=0;i<sum;i++)
        {
            now+=i;
            //右端点向右
            while(now>sum)
            {
            //和大于sum，左端点向右
                now-=j;
                j++;
            }
            if(now==sum)
            {
                //记录一个合法答案
                vector<int>ans;
                for(int k=j;k<=i;k++)
                    ans.push_back(k);
                    a.push_back(ans);
                    //加到答案中
            }
        }
        return a;
    }

};

左右端点都是从1到n，所以时间复杂度O(2*n)
空间复杂度O(n^2)