题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

非常暴力,首先这个一定是一半开始的数依次减，因为最少是两个数的和，
然后就是往后遍历。

时间复杂度

参考文献

java 代码

class Solution {
    public List<List<Integer> > findContinuousSequence(int sum) {
       //暴力解法
       List<List<Integer>> ans = new ArrayList<>();
       List<Integer> ml = new ArrayList<>();
       int n =sum/2+1;
       for(int i=n;i>0;i--)
       {
           int res=sum;
           for(int j=i;j>0;j--)
           {
               ml.add(j);
               res-=j;
               if(res==0) {//结果为0了，把路径加到答案中去
                   List<Integer> mll = new ArrayList(ml);
                   Collections.reverse(mll);
                   ans.add(mll);
                   ml.clear();
                   break;

               }
               if(res>0) continue;//结果大于0，继续加
               if(res<0) {ml.clear();break;}//结果小于0，超过了，直接退出来；
           }
       }
       return ans;
    }
}

算法2

(y总的方法总是好用) $O(n)$

时间复杂度

参考文献

java 代码

class Solution {
    public List<List<Integer> > findContinuousSequence(int sum) {
        List<List<Integer>> ans = new ArrayList<>();
        //用i和j表示从i开始到j的一段区间,且当i增加时j也会增加，这是使用双指针的条件
        //i表示的左起的开头
        for(int i=1,j=1,s=0;i<sum/2+1;i++)
        {
            while(s<sum) s+=j++;
            if(s==sum&&j-i>=1)//如果是s=sum的话，就将结果加进来，
            {
                List<Integer> ml =new ArrayList<>();
                for(int p=i;p<j;p++){
                    ml.add(p);
                }
                ans.add(ml);
            }
            s=s-i;//更新s的值，是因为i增加，j一定是在原有的基础上增加

        }
        return ans;
    }
}