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-/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;}};