题目难度:中等
题目考察:枚举,尺取
题目内容:输出所有和为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)