题目链接

牛客网在线oj题——和为S的连续正数序列

题目描述

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

数据范围：0<n≤100
进阶：时间复杂度 O(n)

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

题目示例

示例1

输入：
9

返回值：
[[2,3,4],[4,5]]

示例2

输入：
0

返回值：
[]

解题思路

我们需要确定连续正数序列的起始位置和终止位置，可以定义起始位置为start，终止位置为end，这个序列为闭区间

计算start和end中所有元素的总和total

1. 如果total小于S，说明序列中的值太小，将end++即可
2. 如果total小于S，说明序列中的值太大，将start++即可
3. 如果total等于S，直接将start和end中所有的元素添加进结果即可

例如：
目标S = 9

此时total = 3， 小于S，end++

此时total = 6， 小于S，end++

此时total = 10， 大于S，start++

此时total = 9 == S，将2，3，4这个序列添加进结果集中，start++，end++

继续上述的操作

此时total = 9 == S，将4，5这个序列添加进结果集中，start++，end++

此时total = 10， 大于S，start++

此时start == end，因此右面不再可能出现和为S的连续正数序列，终止循环

完整代码

import java.util.ArrayList;
public class Solution {
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
       ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        int start = 1;
        int end = 2;
        while(start < end){
            int total = (start + end) * (end - start + 1) / 2;
            if(sum == total){
                ArrayList<Integer> tmp = new ArrayList<>();
                for(int i = start; i <= end; i++){
                    tmp.add(i);
                }
                result.add(tmp);
                start++;
                end++;
            } else if(total < sum){
                end++;
            } else {
                start++;
            }
        }
        return result;
    }
}