和为S的连续正整数序列

题目描述

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

输出描述:

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

解析：

先用直观的求和公式，

复杂度

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int> > ans;
        for(int i=1;i<=sum;i++)
        {
            for(int j=sum;j>i;j--)
            {
                vector<int> list;
                if(j*j-i*i+i+j==sum*2)
                {
                    for(int k=i;k<=j;k++)
                    {
                        list.push_back(k);
                    }
                    ans.push_back(list);
                }
            }
        }
        return ans;
    }
};

实际上有许多是不需要判断的，因为是连续序列，连续序列有一个很好的性质：序列的中位数乘以序列的长度等于序列的和，例如18+19+20+21+22=100，中位数为20，长度为5，则有20×5=100；9+10+11+12+13+14+15+16=100，中位数为12.5，长度为8，则有12.5×8=100.

于是，我们只需要找到序列的长度n，利用S/n求出中位数（当所求值为整数或整数加0.5时才符合题意）。当n为奇数时，中位数为整数，序列起始值为S/n-n/2，终止值为S/n+n/2；当n为偶数时，中位数不是整数，序列起始值为S/n-n/2+0.5，终止值为S/n+n/2-0.5。

由题意知n  2，现在只需求n的最大值，从1加到n序列可取得最大长度，所以n的最大值满足

所以遍历的范围为  ，严格意义上不需要包括，但是取整可能丢失小数部分从而实际值小于，所以代码中包含了。

复杂度为。

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int>> arr;
        if(sum < 2) return arr;
        
        int n = (int)sqrt(2*sum);
        for(int i = n; i >= 2; --i){
            if((n & 1) == 1 && sum % n == 0 || (sum % n) * 2 == n){
                vector<int> list;
                for(int k = 0, startData = sum/i - (i-1)/2; k < i; ++k, ++startData){
                    list.push_back(startData);
                }
                arr.push_back(list);
            }
        }
        return arr;
    }
};

最后

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

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