题解 | #和为S的连续正数序列#

和为S的连续正数序列

https://www.nowcoder.com/practice/c451a3fd84b64cb19485dad758a55ebe

#include <vector>
class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        // write code here
        if (sum == 0) return vector<vector<int>>{};// 剔除空情形
        int l = 1, r = 1;// 题意取值范围1~100,故一开始左右指向都是1
        int tmp_sum = 0;
        vector<int> tmp_v;
        vector<vector<int>> res;
        while(l <= r && r <= sum/2+1)// 保证一直找,并且最大遍历访问也是就sum/2 + 1
        {
            tmp_sum = (l+r)*(r-l+1)/2;//等差数列求和公式理解
            // std::cout << tmp_sum <<" " << i <<" " <<l << " " << r<< std::endl;
            if(sum == tmp_sum)
            {
                for(int j = l; j <= r; ++j)
                {
                    tmp_v.push_back(j);
                }
                if(tmp_v.size() > 1)
                    res.push_back(tmp_v);// 题意至少两个数,故剔除较小值时的异常情况
                tmp_v.clear();
                l++;// 但满足时,需要更新左指向,否则会一直死循环
            }
            else if(tmp_sum < sum)  // 和比目标值小,则右指针右移动
            {
                r++;
            }
            else    // 和比目标值大,则缩减左值向右移动
            {
                l++;
            }
        }
        // std::cout << res.size() << std::endl;
        return res;
    }
};

挤挤刷刷! 文章被收录于专栏

记录coding过程

全部评论

相关推荐

点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务