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. 从 1 开始累加滑动窗口的数字之和,我们称它为总和
  2. 移动窗口时,总和未达到目标值,则向右移动右边界增加总和,接着循环寻找下一个匹配值
  3. 移动窗口时,总和正好等于目标值,则将滑动窗口的数组存储起来。这时不能再向右移动右边界了,因为一旦移动右边界,总和必定超过目标值,无法再次匹配目标值。所以我们应该向右移动左边界,接着循环寻找下一个匹配值
  4. 移动窗口时,总和超过了目标值,右边界显然不能继续向右移动了,因为这和上面说的情况一样,之后无法再次匹配目标,所以我们也应该向右移动左边界,接着循环寻找下一个匹配值

代码:

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

参考

评论