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

剑指 Offer 57 - II. 和为s的连续正数序列 - 力扣（LeetCode）

至少包含两个数，那就是在1-target-1里面进行挑选，而且还得是连续的，所以应该是回溯枚举的思路

先写一个，效率一般

class Solution { public: vector<vector<int>> res; vector<int> tmp; void backtrack(int idx, int sum, int target){ if(sum == target){ res.push_back(tmp); return; } if(sum + idx <= target){ tmp.push_back(idx); backtrack(idx+1, sum+idx, target); }else{ tmp.clear();//全部作废 return; } } vector<vector<int>> findContinuousSequence(int target) { for(int i = 1; i < target; ++i){ backtrack(i, 0, target); } return res; } };

分析一下效率一般的原因，每个数都要考虑作为序列的开头，其实是没有必要的，至少在target/2后面的数就没必要考虑了，那就先优化这部分：

class Solution { public: vector<vector<int>> res; vector<int> tmp; void backtrack(int idx, int sum, int target){ if(sum == target){ res.push_back(tmp); return; } if(sum + idx <= target){ tmp.push_back(idx); backtrack(idx+1, sum+idx, target); }else{ tmp.clear();//全部作废 return; } } vector<vector<int>> findContinuousSequence(int target) { for(int i = 1; i <= target/2; ++i){ backtrack(i, 0, target); } return res; } };

效率还是一般，再优化。。。

其实可以考虑前缀和的思路，因为题目要求是连续的序列，所以可以使用前缀和来表示区间元素的和值，于是就变成了在前缀和数组里面寻找两个差值为target的元素，类似两数之和一样的思路。写出来的代码是这样的，效率极低。。。。

class Solution { public: vector<vector<int>> res; vector<int> tmp; vector<vector<int>> findContinuousSequence(int target) { vector<long> sum(target, 0); //前缀和数组 unordered_map<int, int> m; //记录的是<值，下标> for(int i = 1; i < target; ++i) sum[i] = i + sum[i-1]; for(int i = 0; i < sum.size(); ++i){//这儿枚举的是sum数组 int val = sum[i] - target; //cout << i << " " << sum[i] << " "<< val << endl; if(m.count(val))//进行元素添加 f(m[val], i); m[sum[i]] = i;//这儿key为前缀和，value为下标 } return res; } void f(int l, int r){ tmp.clear(); for(int i = l+1; i <= r; ++i) tmp.push_back(i); res.push_back(tmp); } };

看来还是得换个思路，上面的思路效率低的原因比较明显：重复考虑或者计算太多。

由于所有的数字都是连续的，从1到target-1，所以要计算某一部分的区间和不就是等差数列吗？直接套公式（n(a1 + an)/2）就可以了，什么前缀和数组啥的，都不用，那么使用双指针进行遍历：

class Solution { public: vector<vector<int>> res; vector<int> tmp; vector<vector<int>> findContinuousSequence(int target) { int l = 1, r = 2;//初始区间 while(l < r){ int sum = (l+r)*(r-l+1)/2;//区间和 if(sum == target){//出现一组答案 tmp.clear(); for(int i = l; i <= r; ++i) tmp.emplace_back(i); res.emplace_back(tmp); ++l; } else if(sum < target) ++r;//右边界可以扩展 else ++l;//增加左边界 } return res; } };

上面的代码效率瞬间就上来了。不过还有一种思路就是滑动窗口，本质上和双指针没啥区别：

class Solution { public: vector<vector<int>> res; vector<int> tmp; vector<vector<int>> findContinuousSequence(int target) { int l = 1, r = 2;//初始区间 int sum = l+r; while(l <= target/2){ if(sum == target){//出现一组答案 tmp.clear(); for(int i = l; i <= r; ++i) tmp.emplace_back(i); res.emplace_back(tmp); sum -= l; ++l; } else if(sum < target){ ++r;//右边界可以扩展 sum += r; } else{ sum -= l; ++l;//增加左边界 } } return res; } };