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

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

思路：

dfs:
对于构成的连续序列，只需要枚举到target的一半上取整即可。
每次取path的最后一个元素，枚举这个元素 + 1是否符合
next + cnt <= target

代码：

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int>> findContinuousSequence(int target) {
        for(int i = 1; i < (target + 1) / 2; i++){
            path.push_back(i);
            dfs(target,path,i);
            path.pop_back();
        }
        return res;
    }

    void dfs(int target,vector<int> & path,int cnt){
        if(cnt > target) return;
        if(cnt == target){
            res.push_back(path);
            //path.clear();
            return;
        }
        int next = path.back() + 1;
        if(next + cnt <= target){
            path.push_back(next);
            dfs(target,path,next + cnt);
            path.pop_back();
        }
    }
};

思路：

双指针

对于一个答案 i ~ j，在寻找下一个答案的时候，j' 一定是大于 j的，因为，对 i ~ j求和，答案是target ，那么当i增加到i' 时，j'一定大于j，否则对部分求和小于target.

代码：