剑指 Offer 57 - II. 和为s的连续正数序列

剑指 Offer 57 - II. 和为s的连续正数序列

解法一

暴力枚举

class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        vector<vector<int>> vec;
        vector<int> res;
        int sum=0;
        for (int i = 1; i <= (target-1)/2; i++)
        {
            for (int j=i;; j++)
            {
                sum+=j;
                if(sum>target){
                    sum=0;
                    break;
                }
                if(sum==target){
                    res.clear();
                    for (int k = i; k<=j; k++)
                    {
                        res.push_back(k);
                    }
                    vec.push_back(res);
                    sum=0;
                    break;
                }
            }
            
        }
        return vec;
    }
};

解法二

双指针

class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        vector<vector<int>> vec;
        vector<int> res;
        int sum;
        for (int left=1,right=2; left<right;)
        {
            sum=(left+right)*(right-left+1)/2;
            if(sum==target){
                res.clear();
                for (int i=left; i <=right; i++)
                {
                    res.push_back(i);
                }
                vec.push_back(res);
                left++;
            }
            else if(sum<target) right++;
            else left++;
        }
        return vec;
    }
};
上一篇:Pandas介绍


下一篇:剑指 Offer 57. 和为s的两个数字