题解 | #和为S的连续正数序列#

题目：和为S的连续正数序列

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

返回值描述：

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

暴力法思路分析：通过两层嵌套循环，找出所有符合情况的连续正数序列。

具体思路：首先创建两个空间集合，一个用来存放最终的结果，一个用来临时存放数据集合，设定两个值，分别为i和j。设定i的值不变，将j的值往上加，当不满足条件时，令i的值加1，将j的值重新等于i的值，以此进行判断。

进行第一次判断：Sn的值小于Sum，j++。

……

当Sn的值大于Sum时，i++；

……

输出该值，以此循环进行判断，最终输出所有的值。

Java程序如下所示：

import java.util.ArrayList;
public class Solution {
public ArrayList FindContinuousSequence(int sum) {
    ArrayList res = new ArrayList();//用来存放最终结果
    for(int i = 1;i < sum;i++){ 
    int s = 0; ArrayListre = new ArrayList();//临时存放集合 
    for(int j = i;j < sum;j++){ if(s < sum){ 
        s += j; 
        re.add(j); 
        if(s == sum){ 
            res.add(re); 
            break; } 
    } 
        else break; }
    } 
return res; 
    }
}

该暴力法思路如上表所示，便于理解，但在编写程序时耗费的时间比较长，如下数学公式法则不同，可以通过数学原理进行相应化解处理。

数学公式法思路分析：要计算9~16的和，可以考虑高中的知识点等差数列求和公式法：n(a1+an)/2=Sn，其中n的值为16-9+1，a1的值为9，an的值为16，通过验算可以得到基本的解题方法：

n(a1+an)/2=8*25/2=100。

具体思路：首先定义两个指针，设定初值的大小，其中a1的值为1，a2的值为2，一个指针指向数字1，另一个指针指向数字2，通过不停的循环，循环结束条件为a1的值大于an的值，即a1>an。

由上表可知，第一次循环条件得到的结果为Sn=3，因为目标值Sum=9，所以Sn < Sum，说明最大的值有点小，需要将an的值继续增加到3。

经过比较Sn < Sum，继续增加an的值。

当Sn > Sum说明a1的值有点小，需要将a1的值增大。

如果Sn==Sum就说明找到了连续的数，（2，3，4），就将数装入一个临时的集合当中，把集合整体当成一个值，给最终的容器装入，同时将a1的值继续增大。

经过再次运算寻找最新的集合。

以此类推，找到第二组集合数（4，5），当a1的值大于an的值时，程序结束运算。

Java程序如下所示：

import java.util.ArrayList;
public class Solution {
public ArrayListFindContinuousSequence(int sum) {
    ArrayListres = new ArrayList();//设定最终的存放结果
    int a1 = 1,an = 2;//初始值
    while(an > a1){
        int Sn = (an - a1 + 1)*(an + a1)/2;//求和公式
        if(Sn == sum){
            ArrayListlist = new ArrayList<>();
            for(int i = a1;i <= an;i++){ list.add(i); } res.add(list); a1++; } else if(Sn < sum) an++; else a1++; } return res; }