剑指 Offer 57 - II. 和为 s 的连续正数序列
力扣题目链接[1]
输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
「示例 2：」
输入：target = 15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]
复制
「限制：」
-
1 <= target <= 10^5
思路：
本题可以采用双指针求解。按照题目描述，需要找出所有和为目标值的 「连续正整数」 序列。那么此时声明两个指针，左指针指向 「1」 ，右指针指向 「2」 。同时初始化包括左右指针在内所有连续正整数之和的变量s，默认为 「3」 。指针区间就是一个滑动窗口。
然后判断s和目标值的关系，如果相等，则将滑动窗口内的数字整合成数组，并添加到结果数组中。
s ≥ target
的时候需要将滑动窗口缩小，也就是将左侧的值从s中减去，并右移左指针。
s < target
的时候需要将滑动窗口扩大，也就是将右指针右移，并将右侧的值添加到s中。
双指针
/**
* @param {number} target
* @return {number[][]}
*/
var findContinuousSequence = function(target) {
let i = 1; // 初始化变量
let j = 2;
let s = 3;
let res = []; // 初始化结果数组
while(i < j) {
if (s === target) {
res.push(Array.from({ length: j - i + 1 }).map((_, index) => index + i))
}
if (s < target) {
j++;
s += j;
} else {
s -= i;
i++;
}
}
return res;
};
复制
- 时间复杂度 O(n)。
- 空间复杂度 O(1)。
分析：
当
s === target
时，我们需要将滑动窗口内的元素生成一个数组，并添加到结果数组中。生成的方是通过
map
遍历，将每个元素的值设置为
index + i
，从而得到递增的正整数数组。
还需要注意的是，缩小滑动窗口时，需要先将当前左指针所在的数字从s中减去，再右移左指针。如果先右移左指针的话，就会多减去 「1」 ，导致最终结果异常。同样的，扩大滑动窗口的时候，需要先右移右指针，再将当前右指针所在的数字添加到s中。如果先添加右指针元素的话，就会导致右指针元素重复添加一次，从而少添加1，导致最终结果异常。
总结
本题考查双指针。同时需要注意修改s和指针移动的顺序。如果顺序写反，得到的结果就是错误的。
参考资料
[1]力扣题目链接: https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/eufzm7/