方法一:暴力解法

区间左边界 i

区间右边界 j

用枚举区间[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;
             // 区间 [i j]
             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)

方法二:滑动窗口

解题思路:
连续子序列问题,最优解法就是滑动窗口的使用。
确定左右边界left right,滑动窗口确定区间范围,sum小于target右移,大于则左移,注意等于的时候加入结果的同时要左移缩小边界,继续统计下一组结果


这里的题意隐藏条件 没有给定具体的数组num 我们可以通过下标关联[1,2,3,4,5,6,7....]

代码如下:已经加上详细的注释了

import java.util.ArrayList;
public class Solution {
    public ArrayListFindContinuousSequence(int sum) {
       ArrayList< ArrayList> res = new ArrayList<>();
        // 窗口 win 左边界 left  右边界 right 
        int left = 1;
        int right = 1;
        int win = 0;   // 窗口 win 中数字之和
        while( left <= (sum/2) ){ // left 左边界的有效范围 【有剪枝】 // 一直循环判断 win 和 sum 的大小关系 if(win == sum){ // 把当前的结果收集起来 ArrayListlist = new ArrayList<>();
                for(int i=left;isum){
                //  把窗口中左边的元素去掉 (2个操作)
                win = win - left;
                left++;
            }else{  // win < sum // 窗口值增加 right向右移动 win = win + right; right++; } } return res; } }

图示操作:一直循环着向前进
图片说明
终止条件:有剪枝操作,left <= sum/2
自己可以分 sum 为奇数偶数,得出最终结论。举例即可!

复杂度分析:
时间复杂度 O(N) : 其中 N = sum ;
空间复杂度 O(1) : 只有几个常量而已!