和为s的正整数序列

和为S的连续正数序列

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

1.暴力枚举法的复杂度为o(n)的
2.优化,因为有单调的性质,故将其优化为双指针算法

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int>> ans;
        for(int i=1,j=1,s=1;i<sum;i++){
            while(s<sum) s+=++j;
            if(s==sum && j-i>0){
                vector<int> line;
                for (int k=i;k<=j;k++){
                    line.push_back(k);
                }
                ans.push_back(line);
            }
            s-=i;
        }

        return ans;
    }
};
全部评论

相关推荐

06-25 16:00
武汉大学 Java
工科研究生底薪工资就开3k啊??
机械打工仔:写文章提成的岗位工资低,你怪工科?
点赞 评论 收藏
分享
05-23 20:31
已编辑
武汉大学 Java
内向的柠檬精在研究求...:注意把武大标粗标大 本地你俩不是乱杀
实习进度记录
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

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