和为S的子序列

题目描述

小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。

但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。

没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。

现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!

输出描述:

输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序

题解

滑动窗口

就是根据窗口内的值来确定窗口的位置和宽度

用两个指针，一个指向子序列的起点 start，一个指向子序列的终点 end

当窗口内的值大于S，end 右移

反之，start左移

如果窗口内的值 == S，说明已找到一个子序列，输出，然后start左移找下一个子序列

public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
    if (sum == 0)
        return null;

    ArrayList<ArrayList<Integer>> res = new ArrayList<>();

    //滑动窗口的初始位置
    int start = 1, end = 2;

    while (start < end) {
        //递增数列求和,+1是为了保证无论奇偶都能取到中间值
        int subSum = (start + end) * (end - start + 1) / 2;

        if (subSum == sum) {
            res.add(addRes(start, end));
            start++;
        } else if (subSum < sum) {
            end++;
        } else {
            start++;
        }
    }

    return res;
}

private ArrayList<Integer> addRes(int start, int end) {
    ArrayList<Integer> res = new ArrayList<>();
    for (int i = start; i <= end; i++) {
        res.add(i);
    }
    return res;
}