首页 > Windows开发 > 详细

acwing 76. 和为S的连续正数序列

时间:2019-09-04 17:42:56      阅读:68      评论:0      收藏:0      [点我收藏+]

地址 https://www.acwing.com/problem/content/description/72/

输入一个正数s,打印出所有和为s的连续正数序列(至少含有两个数)。

例如输入15,由于1+2+3+4+5=4+5+6=7+8=15,所以结果打印出3个连续序列1~5、4~6和7~8。

样例

输入:15

输出:[[1,2,3,4,5],[4,5,6],[7,8]]

  

双指针指向一个连续空间 如果和小了 则向右扩展 如果和大了 则弹出左边的值

class Solution {
public:
    
    
vector<vector<int> > vv;

vector<vector<int> > findContinuousSequence(int sum) {
    int l = 0; int r = 0;
    vector<int> nums;
    for (int i = 1; i <= sum / 2 + 1; i++) {
        nums.push_back(i);
    }

    int tmpSum = nums[l];

    while (l < nums.size() && r < nums.size() && l <= r) {
        if (tmpSum > sum) { tmpSum -= nums[l]; l++; continue; }
        else if (tmpSum < sum) {
            tmpSum += nums[r+1]; r++; continue;
        }
        else if (tmpSum == sum) {
            vector<int> v;
            for (int i = l; i <= r; i++) {
                v.push_back(nums[i]);
            }
            vv.push_back(v);
            if (r < nums.size() - 1)
                tmpSum += nums[r + 1]; 
            r++; continue;
        }
    }

    return vv;
}


};

 

acwing 76. 和为S的连续正数序列

原文:https://www.cnblogs.com/itdef/p/11460354.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!