Sword to Offer-57.2 和为S的连续正数序列 ❀❀

14 May 2020 in Algorithm

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

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

解题思路：

变长滑动窗口问题：
1、初始begin和end为1和2，循环条件为begin<=sum/2；
2、当前窗口内数字总和<sum时，end++，当前窗口内数字总和>sum时，begin++；
3、恰好=sum时找到了一个满足条件的序列，此时新建一个临时ArrayList将窗口内的值添加到其中，让将该ArrayList添加到需要返回的ArrayList列表内；
4、找到满足的序列后，begin++，end++继续搜索； 5、注意指针移动和修改当前sum值的先后顺序，begin指针应先修改sum再移动，end指针应先移动再修改sum值。

问题图解：

AC代码：

// Find All Consecutive Sequences of Positive Number Sum S

import java.util.ArrayList;

public class Solution {
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> seqs = new ArrayList<>();
        int begin = 1, end = 2;
        int curSum = 3;
        while (begin <= sum/2) {
            if (curSum > sum) {
                curSum -= begin;
                begin++;
            }
            else if (curSum < sum) {
                end++;
                curSum += end;
            }
            else {
                ArrayList<Integer> seqSingle = new ArrayList<>();
                for (int i=begin; i<=end; i++) {
                    seqSingle.add(i);
                }
                seqs.add(seqSingle);
                curSum -= begin;
                begin++;
                end++;
                curSum += end;
            }
        }
        return seqs;
    }
}

补充说明：

• 这里是牛客编码链接