LeetCode笔记:和为s的连续正数序列
问题
输入一个正整数 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
解法
思路:
采用滑动窗口的思想
- 从 1 开始累加滑动窗口的数字之和,我们称它为总和
- 移动窗口时,总和未达到目标值,则向右移动右边界增加总和,接着循环寻找下一个匹配值
- 移动窗口时,总和正好等于目标值,则将滑动窗口的数组存储起来。这时不能再向右移动右边界了,因为一旦移动右边界,总和必定超过目标值,无法再次匹配目标值。所以我们应该向右移动左边界,接着循环寻找下一个匹配值
- 移动窗口时,总和超过了目标值,右边界显然不能继续向右移动了,因为这和上面说的情况一样,之后无法再次匹配目标,所以我们也应该向右移动左边界,接着循环寻找下一个匹配值
代码:
/**
* @param {number} target
* @return {number[][]}
*/
var findContinuousSequence = function (target) {
let start = 1; //滑动窗口开始位置,即左边界
let end = 1; //滑动窗口结束位置,即右边界
let sum = 0; //滑动窗口的数字之和,用于和target比较
result = []; //结果数组
// 开始位置,一旦start比target的一半大,start + start + 1 就会超出target的大小,无需再循环了
while (start <= target / 2) {
// 未达到目标值,继续寻找
if (sum < target) {
sum += end;
end += 1;
}
// 超过目标值,左边界右移
else if (sum > target) {
sum -= start;
start += 1;
}
// 等于目标值,存储起来,并且左边界右移
else {
//通过开始结束值获取递增数组 如:2,4 => [2,3]
let res = [...new Array(end).keys()].slice(start);
result.push(res);
sum -= start;
start += 1;
}
}
return result;
};
评论