剑指 Offer 57 - II. 和为 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

解题思路

这道题是个滑动窗口，关键点在于：

左右窗口
窗口里的数之和

function findContinuousSequence(target: number): number[][] {
  // 定义返回数组
  let res = [];
 
  // 因为至少要含有两个数
  if (target <= 2) return res;
 
  // target从1开始
  let l = 1;
  let r = 1;
 
  // 窗口和
  let sum = 1;
 
  // 终止条件：l > target / 2
  while (l <= target / 2) {
    if (sum === target) {
      // 这里创建了一个数组，是因为结果需要为一个二维数组
      let temp = [];
      for (let i = l; i <= r; i++) {
        temp.push(i);
      }
      res.push(temp);
    }
    // 窗口和 < target，窗口需要扩大
    if (sum < target) {
      r++;
      sum += r;
    } else {
      // 窗口和 > target，窗口需要缩小
      // 这里的缩小是指：将上一次窗口和中的某个数减掉，相当于窗口进行了缩小
      sum -= l;
      l++;
    }
  }
 
  return res;
}