求和为S的所有连续正数数列

今天在牛客上看到一道题：

题目描述

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

输出描述:

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

思路很简单：

定义两个指针start < end，一起从前往后扫描

sum>S,start++，

sum<S,end++，

sum==S, 判断start+1<end?start++:break,这里如果start+1<end,那么往后走肯定结果也是大于S的，所以直接 跳出循环就可以了。

还有一个值得注意的地方，就是每次计算sum的时候，可以在上次的基础上进行计算，这样更加优化。

贴上AC代码，因为最近一直在学node，所以编程题都用node来写：

function FindContinuousSequence(sum)
{
    if(sum <= 2)
        return [];
    var result = [];
    // write code here
    var a = 1,
        b = 2,
        s = 3;
    while(a <= Math.floor(sum/2)){
        if(s < sum){
            b++;
            s += b;
        }else if(s > sum){
            s -= a;
            a++;
        }else{
            var temp = [];
            for(var i=a;i <= b;i++)
                temp.push(i);
            result.push(temp);
            if(a+1 < b){
                s -= a;
           		a++;
            }else{
                break;
            }
        }
    }
    return result;
}
module.exports = {
    FindContinuousSequence : FindContinuousSequence
};

最后

以上就是冷傲音响为你收集整理的求和为S的所有连续正数数列的全部内容，希望文章能够帮你解决求和为S的所有连续正数数列所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。