1、和为S的连续整数序列
描述
小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。
没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!

返回值描述：
输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序。

示例
输入：9
返回值：[[2,3,4],[4,5]]

方法一：滑动窗口
核心思想：
由题意可知，需要根据指定的数，求解连续的正数序列。因此此序列可以看做是等差序列，其中公差为1。由等差序列公式可知：Sn=(p1+pn)*(pn-p1+1)/2。因此本题可以采用滑动窗口来求解正数序列。窗口左侧为p1，窗口右侧为pn，窗口中元素的和为Sn，其中窗口中的序列服从等差序列。初始时，左侧窗口值为1，右侧窗口值为2。求解窗口中的和Sn，并和目标值target进行比较，比较结果有如下三种情况：

1）当 Sn>target 时：左侧窗口p1向右滑动，即元素减少一个，继续求和跟target比较
2）当 Sn=target 时：窗口内的元素即为求解的子序列和，将窗口中的元素存放到二维数组中（每个序列存放在一维数组）。同时窗口pn向右滑动，继续接收新的子序列。
3）当 Sn<target 时：右侧窗口pn向右滑动，即元素增加一个，继续求和跟target比较 循环结束边界条件： 窗口一直缩小到一个元素的时候即退出循环 (题目中序列元素最少为2个，因次p1<pn即为循环条件，等于的时候则退出循环，因为等于的时候窗口缩小到一个元素了)
图解：
图片说明
核心代码： 

vector<vector<int> > FindContinuousSequence(int sum) {
    vector<vector<int>> result;
    int p1=1,pn=2,Sn=0,i;    //p1窗口左侧值，pn窗口右侧值，Sn记录窗口元素和
    while(p1<pn){ 
        Sn=(p1+pn)*(pn-p1+1)/2;   //等差数列求窗口值的和 
        if(Sn>sum){         //窗口值大于目标值，则需要左侧窗口向右滑动缩小窗口
            p1++;
        }else if(Sn == sum){     //窗口值等于目标值，则保存目标窗口序列，同时右侧窗口向右滑动，继续循环其他符合条件的目标窗口序列
            vector<int> tmp;
            for(i=p1;i<=pn;i++)
                v.push_back(i);
            result.push_back(tmp);
            pn++;
        }else{       //窗口值小于目标值，则需要右侧窗口向右滑动缩扩大窗口
            pn++;
        }
    }
    return result;
}

时间复杂度O(n)
空间复杂度(1)


方法二：窗口间隔法
核心思想：
由连续子序列的和为target可知，因为序列满足公差为1的等差数列，因此可以根据推到公式得出
Sn=(p1+pn)(pn-p1+1)/2 (1)
假设窗口间隔为dis，则 dis=pn-p1 (2)
由(1)和(2)得出 Sn = (2p1+dis)(dis+1)/2 => p1 = [Sn-dis(dis+1)/2]/(dis+1) (3)
由公式(3)可知，符合的窗口序列必须满足以下条件：
1）Sn > dis(dis+1)/2
2）Sn-dis(dis+1)/2 除以 dis+1必须为正整数

结果处理：由于求出的序列间隔是从小到大，序列间隔越小表示序列中的数值越大，题目要求的实际序列间按照开始数字从小到大的顺序，因此需要将结果序列键进行逆置操作

图解：
图片说明

核心代码：

vector<vector<int> > FindContinuousSequence(int sum) {
    vector<vector<int>> result;
    int dis=1,p1=1,i;     //dis记录窗口的间隔，p1记录窗口左侧元素
    while(dis*(dis+1)/2 < sum){      //满足第一个条件
        if((sum - dis*(dis+1)/2) % (dis+1) == 0){      //满足第二个条件
            p1 = (sum - dis*(dis+1)/2) / (dis+1);      //求窗口的左侧元素
            vector<int> v;
            for(i=p1;i<=p1+dis;i++)     //保存符合条件的序列
                v.push_back(i);
            result.push_back(v);
        }
        dis++;
    }
    reverse(result.begin(), result.end());     //序列间逆置处理
    return result;
}

时间复杂度O(n)
空间复杂度O(1)