剑指Offer - 面试题57 - II. 和为s的连续正数序列（滑动窗口）

1. 题目

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。

序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

示例 1： 输入：target = 9 输出：[[2,3,4],[4,5]]示例 2： 输入：target = 15 输出：[[1,2,3,4,5],[4,5,6],[7,8]]限制： 1 <= target <= 10^5

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

• 滑动窗口 [l,r]，其内的和为sum
• sum < target, r++
• sum > target, l++
• sum = target, 写入答案，l++

class Solution { public:vector<vector<int>> findContinuousSequence(int target) {vector<vector<int>> ans;int l = 1, r = 0, sum = 0, i;while(r <= (target+1)/2)//r最多不会超过一半{if(sum == target){ //相等vector<int> t;for(i = l; i <= r; ++i)t.push_back(i);if(t.size() > 1)ans.push_back(t);sum -= l;//更新左边界，让他少一个数l++;}while(sum > target){ //大了，减少左边的数sum -= l;l++;}while(sum < target){ //小了，增加右边的数r++;sum += r;}}return ans;} };

总结

以上是生活随笔为你收集整理的剑指Offer - 面试题57 - II. 和为s的连续正数序列（滑动窗口）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。