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

地址 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的连续正数序列

上一篇:持续集成高级篇之Jenkins windows/linux混合集群搭建(二)


下一篇:idea、vscode快捷键