和为S的连续正数序列

问题描述

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

思路分析

核心思想就是通过两个变量small（最小值）和big（最大值）来控制，比如s为12，起始samll为1，big为2，和为3小于12，说明big需要后移一位，此时为{1,2,3}为6，小于12，big在增大直至{1,2,3,4,5}为15大于12，说明最小值应该后移，所以为{2,3,4,5}，继续后移{3,4,5}满足，找到了，思路大致就是这样，但是small移动时不能超过（sum+1）/2，也就是平均值，因为超过平均值后面肯定会大于s了

码上有戏

public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
      ArrayList<ArrayList<Integer>> sqList=new ArrayList<ArrayList<Integer>>();
       if(sum<3)return sqList;
       int small=1;
       int big=2;
       int curSum=small+big;
       int middle=(1+sum)/2;
       while(small<middle){
           ArrayList<Integer> sq=new ArrayList<Integer>();
          if(curSum==sum){
               for(int i=small;i<=big;i++)
                   sq.add(i);
           }
           while(curSum>sum&&small<middle){
               curSum-=small;
               small++;
               if(curSum==sum){
               for(int i=small;i<=big;i++)
                   sq.add(i);
           }
           }

       if(sq.size()>0)sqList.add(sq);
       big++;
       curSum+=big;
       }
       return sqList;
   }