剑指offer-41

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

最直接 最简单的方法：
for-for O(n^2)即可

标准解法：滑动窗口。
前后指针，当窗口内的数字之和（因为是连续的数字，用求和公式即可）小于sum就移动前指针，大于sum就移动后指针，等于就保存结果并把前后指针都往前移动（移动均为前移1位）。

坑点：起点是1，不包括0

简单的方法

import java.util.ArrayList;
public class Solution {
    public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
        for(int i=1;i<sum;i++){
            int temp = 0;
            int j=i;
            for(;j<=sum;j++){
                temp+=j;
                if(temp>=sum){
                    break;
                }
            }
            if(temp==sum){
                ArrayList<Integer> list = new ArrayList<>();
                for(int k=i;k<=j;k++){
                    list.add(k);
                }
                ans.add(list);
            }
        }
        return ans;
    }
}

标准解法

import java.util.ArrayList;
public class Solution {
    int rangeSum(int s, int e){
        int l = e-s+1;
        return (s+e)*l/2;
    }
    public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
        int slow = 1;
        int fast = 2;

        while(fast<=sum&&slow<fast){
            int tempSum = rangeSum(slow, fast);
            if(tempSum==sum){
                ArrayList<Integer> list = new ArrayList<>();
                for(int k=slow;k<=fast;k++){
                    list.add(k);
                }
                ans.add(list);
                slow++;
                fast++;
            }else if(tempSum>sum){
                slow++;
            }else {
                fast++;
            }
        }
        return ans;
    }
}