题目链接

题目描述

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

返回值描述:
输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序。
例如和为 100 的连续序列有：
[9, 10, 11, 12, 13, 14, 15, 16]
[18, 19, 20, 21, 22]

解题思路

方法一：枚举+暴力

记录left为1,right为sum
从left开始逐个加，判断是否有等于sum的，如果有，则成立，将序列加入数组，如果和大于sum则跳到下一步
letf逐步右移。

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int> > vv;
        if(sum<=0)
            return vv;
        int left = 1,right = sum;
        while(left<right){
            vector<int> v;
            int s=0;
            for(int i = left;i<right;++i){
                s += i;
                v.push_back(i);
                if(s==sum){
                    vv.push_back(v);
                    break;
                }else if(s>sum){
                    break;
                }
            }
            left++;
        }
        return vv;
    }
};

时间复杂度：O(N^2)
空间复杂度：O(1)

方法二：滑动窗口（双指针）

如何用滑动窗口解这道题
要用滑动窗口解这道题，我们要回答两个问题：
第一个问题，窗口何时扩大，何时缩小？
第二个问题，滑动窗口能找到全部的解吗？
对于第一个问题，回答非常简单：
当窗口的和小于 target 的时候，窗口的和需要增加，所以要扩大窗口，窗口的右边界向右移动
当窗口的和大于 target 的时候，窗口的和需要减少，所以要缩小窗口，窗口的左边界向右移动
当窗口的和恰好等于 target 的时候，我们需要记录此时的结果。设此时的窗口为 [i, j)，那么我们已经找到了一个 i 开头的序列，也是唯一一个 i 开头的序列，接下来需要找 i+1开头的序列，所以窗口的左边界要向右移动

对于第二个问题，我们可以稍微简单地证明一下：
57.2 和为 S 的连续正数序列 - 图1
我们一开始要找的是 1 开头的序列，只要窗口的和小于 target，窗口的右边界会一直向右移动。假设 1+2+⋯+8 小于 target，再加上一个 9 之后，发现 1+2+⋯+8+9 又大于 target 了。这说明 1 开头的序列找不到解。此时滑动窗口的最右元素是 9。
接下来，我们需要找 2 开头的序列，我们发现，2+⋯+8<1+2+⋯+8以此类推，滑动窗口的左右边界都不需要向左移动，所以这道题用滑动窗口一定可以得到所有的解。时间复杂度是 O(n)。

class Solution {
public:
    vector<vector<int>> FindContinuousSequence(int target) {
        int i = 1; // 滑动窗口的左边界
        int j = 1; // 滑动窗口的右边界
        int sum = 0; // 滑动窗口中数字的和
        vector<vector<int>> res;

        while (i <= target / 2) {
            if (sum < target) {
                // 右边界向右移动
                sum += j;
                j++;
            } else if (sum > target) {
                // 左边界向右移动
                sum -= i;
                i++;
            } else {
                // 记录结果
                vector<int> arr;
                for(int k = i; k < j; k++){
                    arr.push_back(k);
                }
                res.push_back(arr);
                // 左边界向右移动
                sum -= i;
                i++;
            }
        }
        return res;
    }
};