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

101 阅读 0 评论 67 点赞

我是靠谱客的博主狂野火龙果，这篇文章主要介绍剑指Offer - 面试题57 - II. 和为s的连续正数序列（滑动窗口），现在分享给大家，希望可以做个参考。

1. 题目

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

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

复制代码

1
2
3
4
5
6
7
8
9
10
11
示例 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++

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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;
    }
};