题目描述

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

解法一：

暴力遍历，遍历数组，针对遍历到的每个数字，遍历其后面的数字，直到序列大于或等于S。时间复杂度O（n2），不推荐。

public class Solution {
    public static ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        for(int i = 1; i < sum; i++) {
            int count = 0;
            ArrayList<Integer> list = new ArrayList<Integer>();
            for(int j = i; j < sum; j++) {
                list.add(j);
                count += j;
                if(count == sum) {
                    result.add(list);
                    break;
                }
                if(count > sum)
                    break;
            }
        }
        return result;
    }
}

解法二：

设置两个指针low和high分别指向1和2，通过high++计算low与high间的序列和，
若low + high == sum， 则将序列记录下来，low++
若low + high > sum, 则low++
若low + high < sum, 则high++

时间复杂度为O（N）

public class Solution {
    public static ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        int low = 1, high = 2;
        //循环次数控制，不需要low < sum
        while(low < (1 + sum) / 2) {
            int count = (low + high) * (high - low + 1) / 2;
            if(count == sum) {
                ArrayList list = new ArrayList<Integer>();
                for(int i = low; i <= high; i++) {
                    list.add(i);
                }
                result.add(list);
                low++;
            }
            else if(count < sum)
                high++;
            else 
                low++;
        }
        return result;
    }
}

计算时的求和语句：int count = (low + high) * (high - low + 1) / 2;若low与high相差较大时，该乘法比使用循环加法要快。
如果要使用循环加法,可以进行优化，在之前的和的基础上进行运算，避免大量重复计算。

public class Solution {
    public static ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        int low = 1, high = 2;
        //循环次数控制，不需要low < sum
        int count = low + high;
        while(low < (1 + sum) / 2) {
            while(count < sum) {
                high++;
                count += high;
            }
            if(count == sum) {
                ArrayList list = new ArrayList<Integer>();
                for(int i = low; i <= high; i++) {
                    list.add(i);
                }
                result.add(list);
            }
            count -= low;
            low++;
        }
        return result;
    }
}

解法三：

直接利用数学方法。
count = (low + high) (high - low + 1) / 2
推出(low + high) (high - low + 1) = 2 * count
设(low + high) (high - low + 1) = k * l （k >= l)
则low + high = k，high - low + 1 = l
推出
high = (k + l -1) / 2
low = (k - l + 1) / 2
我们可以推算出k与l，继而获得low与high

public class Solution {
    public static ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        int max = (int)Math.sqrt(2 * sum);
        for(int l = max; l > 1; l--) {
            if((2 * sum) % l == 0) {
                int k = (2 * sum) / l;
                if((k + l) % 2 == 1) {
                    int low = (k - l + 1) / 2;
                    int high = (k + l - 1) / 2;
                    ArrayList<Integer> list = new ArrayList<Integer>();
                    for(int i = low; i <= high; i++) 
                        list.add(i);
                    result.add(list);
                }
            }
        }
        return result;
    }
}

由于k与l越接近时low越小，导致获得的list顺序也是按照low从小到达的顺序获得的，满足题目要求。
时间复杂度为O（logN）