和为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;
    }
};
全部评论

相关推荐

1 收藏 评论
分享
牛客网
牛客企业服务