描述

这是一篇针对初学者的题解。共用三种方法解决。
知识点：数学，前缀和，滑动窗口
难度：一星

题解

题目抽象：给定一个1到sum的序列，求所有和为sum的连续序列。

方法一：暴力方法

求和为sum的连续子序列，可用暴力方法，
算法步骤：

1. 用指针i枚举目标序列的左边界
2. 用指针j枚举目标序列的右边界
3. 用指针k枚举区间[i, j]，来计算区间和，看是否等于目标sum。
   代码如下：

   class Solution {
   public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int>> ret;
        // 左边界
        for (int i=1; i<=sum/2; ++i) { 
            // 右边界
            for (int j=i+1; j<sum; ++j) {
                int tmp = 0;
                // 求区间和
                for (int k = i; k<=j; ++k) {
                    tmp += k;
                }
                if (sum == tmp) {
                    vector<int> ans;
                    for (int k=i; k<=j; ++k) ans.push_back(k);
                    ret.push_back(ans);
                }
                else if (tmp > sum) {
                    break;
                }
            }
        }
        return ret;
    }
   };

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

方法二：前缀和

对于求一个区间和，一贯的优化技巧是使用前缀和。比如：
sum[i]表示前i个数的和。比如sum[1] = 1,表示前一个数的和为1，sum[2] = 3, 表示前2个数的和为3.现在我们要求区间[2,4]表示求第2,3,4个数的和，就等于sum[4] - sum[1] = 9
代码中我们用一个变量来模拟这个前缀和。
代码如下：

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int>> ret;
        int tmp = 0;
        for (int i=1; i<=sum/2; ++i) {
            for (int j=i; j<sum; ++j) {
                tmp += j;
                if (sum == tmp) {
                    vector<int> ans;
                    for (int k=i; k<=j; ++k) ans.push_back(k);
                    ret.push_back(ans);
                }
                else if (tmp > sum) {
                    // 提前剪枝
                    tmp = 0;
                    break;
                }
            }
        }
        return ret;
    }
};

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

方法三：滑动窗口

知识补充：

1. 什么是滑动窗口？
   顾名思义，首先是一个窗口，既然是一个窗口，就需要用窗口的左边界i和右边界j来唯一表示一个窗口，其次，滑动代表，窗口始终从左往右移动，这也表明左边界i和右边界j始终会往后移动，而不会往左移动。
   这里我用左闭右开区间来表示一个窗口。比如
   

2. 滑动窗口的操作

• 扩大窗口，j += 1
• 缩小窗口，i += 1
  算法步骤：

1. 初始化，i=1,j=1, 表示窗口大小为0
2. 如果窗口中值的和小于目标值sum， 表示需要扩大窗口，j += 1
3. 否则，如果狂口值和大于目标值sum，表示需要缩小窗口，i += 1
4. 否则，等于目标值，存结果，缩小窗口，继续进行步骤2,3,4

这里需要注意2个问题：

1. 什么时候窗口终止呢，这里窗口左边界走到sum的一半即可终止，因为题目要求至少包含2个数
2. 什么时候需要扩大窗口和缩小窗口？解释可看上述算法步骤。

代码如下：

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int>> ret;
        int l = 1, r = 1;
        int tmp = 0;
        while (l <= sum / 2) {
            if (tmp < sum) {
                tmp += r;
                ++r;
            }
            else if (tmp > sum) {
                tmp -= l;
                ++l;
            }
            else {
                vector<int> ans;
                for (int k=l; k<r; ++k) 
                    ans.push_back(k);
                ret.push_back(ans);
                tmp -= l;
                ++l;
            }
        }
        return ret;
    }
};

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