和为连续的正整数序列

题目：
小明很喜欢数学,有一天他在做数学作业时,要求计算出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>> res;
        if(sum < 3)
            return res;

        int left = 1;//初始左指针
        int right = 2;//初始右指针
        int sum1 = left+right;//左右指针间的区间和
        while(left<right)
        {
            vector<int> tmp;
            sum1 = sumofrange(left, right);
            if(sum1 < sum)//当前区间和小于sum
                right++;
            else if(sum1 == sum){//当前区间和等于sum
                Insert(left, right, tmp);
                res.push_back(tmp);
                left++;
            }
            else//当前区间和大于sum
                left++;
        }
        return res;
    }

    int sumofrange(int left, int right){//求区间为[left,right]的和
        return (left+right)*(right-left+1)/2;
    }

    void Insert(int left, int right, vector<int>& v){//将[left,right]范围的数字插入到v中
        for(int i=left; i<=right; ++i){
            v.push_back(i);
        }
    }
};

最后

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

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