《剑指offer第二版》面试题57 题目二：和为s的连续正数序列

题目描述

• 输入一个正整数s，打印出所有和为s的连续正整数序列（至少包含两个数字）。例如输入15，所以打印出3个连续序列（1，2，3，4，5）（4，5，6）（7，8）

解题思路

1. 用连个数small和end表示序列的最小值和最大值。small到big序列的连续和用sum表示。
2. 如果sum大于s，则small增加。
3. 如果sum小于s，则增加big。
4. 如果sum等于s，则保存这个序列。此时再增大end。
5. 因为序列里至少有连个数字，则small能增加到的最大值是(1+s)/2。

代码

ArrayList<ArrayList<Integer>> findContinuousSequences(int sum){
    if (sum <= 2) {
        return null;
    }
    ArrayList<ArrayList<Integer>> result = new ArrayList<>();
    int begin = 1;
    int end = 2;

    int curSum = begin + end;
    while (begin <= (sum + 1) / 2 && begin < end) {
        if (curSum > sum) {
            curSum = curSum - begin;
            begin ++;
        } else if (curSum < sum) {
            end ++;
            curSum = curSum + end;
        } else {
            result.add(createList(begin, end));
            end ++;
            curSum = curSum + end;
        }
    }
    return result;
}
ArrayList<Integer> createList(int start , int end) {
    ArrayList<Integer> list = new ArrayList<>();
    while (start <= end) {
        list.add(start);
        start ++;
    }
    return list;
}