剑指Offer——和为S的连续正数序列

题目描述

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

输入
9
返回值
[[2,3,4],[4,5]]

题解

循环+等差数列求和

import java.util.ArrayList;
public class Solution {
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>>res=new ArrayList<>();
        for(int left=1;left<=sum/2;++left){
           for(int right=left+1;right<=sum;++right){
               if(sum(left,right)==sum){
                   ArrayList<Integer>temp=new ArrayList<>();
                   for(int i=left;i<=right;++i){
                       temp.add(i);
                   }
                   res.add(temp);
               }
           }
       }
        return res;
    }
    private int sum(int left,int right){
        int sum= right*(right+1)/2-left*(left-1)/2;
        return sum;
    }
}

滑动窗口

import java.util.ArrayList;
public class Solution {
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>>res=new ArrayList<>();
        int left=1,right=1;// left表示开始，right找右边界
        while(left<=sum/2){
            int tempSum=sum(left,right);
            if(tempSum<sum){
                ++right;// 不够就继续扩张
            }else if(tempSum>sum){
                ++left;// 多了，说明以left开始找不到和为S的连续序列
            }else{
                ArrayList<Integer>temp=new ArrayList<>();
                for(int i=left;i<=right;++i){
                    temp.add(i);
                }
                res.add(temp);
                ++left;// 找到了，下一个开始
            }
        }
        return res;
    }
    private int sum(int left,int right){
        int sum= right*(right+1)/2-left*(left-1)/2;
        return sum;
    }
}