LeetCode笔记：和为s的连续正数序列

#leetcode

问题

输入一个正整数 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;
};

参考

评论