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

和为S的连续正数序列

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

第七十三题 好题
双指针 指向左右边界
如果小于sum 右指针右移,如果大于sum左指针右移

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        // 例子:234 45
        // 先找到最开始的234 返回 然后删除2 往后判断 删除3 往后判断 得到5可以。
        vector<vector<int>> retans;
        int p=1,q=1;
        int temp=0;
        
        // 因为至少两个数,所以左边界肯定小于sum的一半
        while(p<=sum/2){
            // 如果加起来的和小于sum,则扩充右边界
            if(temp<sum){
                temp+=q;
                q++;
            }
            // 如果加起来的和大于sum,则删除最左边一个,即左指针p++
            else if(temp > sum)
            {
                temp-=p;
                p++;
            }
            // 如果结果是sum,则根据左右界限,吧pq存到一维数组中,再把数组存到返回答案中
            else if(temp==sum)
            {
                vector<int>tempans;
                for(int j=p;j<q;j++)
                    tempans.push_back(j);
                retans.push_back(tempans);
                // 此时找到了234 然后删除掉最左边的指针,在继续向后遍历
                // 变为34 < 9,则变为345
                // 345 > 9 删除3,得到45
                // 45符合要求,存入,变为5....再向后遍历直到循环结束
                temp-=p;
                p++;
            }
        }
        return retans;
    }
};

题解 文章被收录于专栏

一遍做剑指offer 一边保存做题步骤 并附带详细注释哦

全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 16:15
我应届生,去年10月份开始在这家公司实习,到今年10月份正好一年想(实习+试用期),在想要不要提前9月份就离职,这样好找工作些,但又差一个月满一年,又怕10月份国庆回来离职,容易错过了下半年的金九银十,到年底容易gap到年后
小破站_程序员YT:说这家公司不好吧,你干了快一年 说这家公司好吧,你刚毕业就想跑路说你不懂行情吧,你怕错过金九银十说 你懂行情吧,校招阶段在实习,毕业社招想换工作 哥们,我该怎么劝你留下来呢
应届生,你找到工作了吗
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
昨天 11:15
点赞 评论 收藏
分享
06-26 22:20
门头沟学院 Java
码农索隆:让你把简历发给她,她说一些套话,然后让你加一个人,说这个人给你改简历,然后开始卖课
我的求职精神状态
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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