即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

41、与为S的连续正数序列

编程语言 buki26 8℃ 0评论

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

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

把这个题和之前的某个题混了,想了好久好久做不出来。。。

思路:还是动态规划问题,用双指针


设置begin和end指针,分别指向序列的最小值和最大值,开始分别为1和2,循环判断,如果和大于sum则后移begin指针,小于则继续后移end指针。


循环的终止条件:begin>(sum+1)/2或end>sum

代码:

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int> > res;
        if(sum < 3)
            return res;
        int begin = 1;
        int end = 2;
        int cursum = begin + end;
        int mid = (sum+1)/2;
        while(begin < mid && end < sum){
            //如果cursum大,begin指针后移
            while(cursum > sum){
                cursum -= begin;
                begin++;
            }
            if(cursum==sum){
                insertres(begin,end,res);
            }
            //注意这里应该是end先自加后计算cursum
            end++;
            cursum += end;
        }
        return res;
    }

    void insertres(int begin,int end,vector<vector<int> > &res){
        vector<int> temp;
        for(int i = begin;i <= end;i++){
            temp.push_back(i);
        }
        res.push_back(temp);
    }
};

转载请注明:CodingBlog » 41、与为S的连续正数序列

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情