剑指Offer（四十一）-- 和为S的连续正数序列

代码已经同步到刷题仓库：CodeSolution 仓库地址：https://github.com/Damaer/CodeSolution 文档地址：https://damaer.github.io/CodeSolution/ 如果有图片，图片都是draw.io绘制，在/drawio文件夹下。

题目描述

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

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

示例1

输入

9

返回值

[[2,3,4],[4,5]]

思路以及解答

第一种思路：

针对每一个索引起点，都计算后续的连续子数组的和，并且将元素存到临时list中。

• 如果和不超过sum,那么就继续往后面遍历；
• 如果和等于sum，则说明该连续子数组满足条件，将临时list添加到结果集中
• 如果和大于sum，则说明连续子数组已经超过，该索引起点的不满足条件，直接break。

注意的是，起点我们只需要遍历到sum/2的位置即可，因为大于sum/2的索引，任何两个数的和都大于sum，不符合条件。

代码如下：

import java.util.ArrayList;
public class Solution {
    public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> results= new ArrayList<>();
        for(int start = 1;start<=sum/2;start++){
            int tempSum = 0;
            ArrayList<Integer> integers = new ArrayList<>();
            for (int j=start;j<sum;j++){
                integers.add(j);
                tempSum = tempSum+j;
                if(tempSum==sum){
                    results.add(integers);
                    break;
                }else if(tempSum>sum){
                    break;
                }
            }
        }
        return results;
    }
}

【作者简介】： 秦怀，公众号【秦怀杂货店】作者，技术之路不在一时，山高水长，纵使缓慢，驰而不息。写好每一篇文章，期待和你们一起交流。

此文章仅代表自己（本菜鸟）学习积累记录，或者学习笔记，如有侵权，请联系作者核实删除。人无完人，文章也一样，文笔稚嫩，在下不才，勿喷，如果有错误之处，还望指出，感激不尽~

- END -