题解 | #和为S的连续正数序列#

方法一：暴力解法

区间左边界 i

用枚举区间[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;
 }
};

方法二：滑动窗口

这里的题意隐藏条件 没有给定具体的数组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) : 只有几个常量而已！