题目描述

小明很喜欢数学,有一天他在做数学作业时,要求计算出 9~16 的和,他马上就写出了正确答案是 100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为 100(至少包括两个数)。没多久,他就得到另一组连续正数和为 100 的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为 S 的连续正数序列 ?

限制：

1 <= S <= 10^5

测试用例

用例 1：

• 输入：target = 9
• 输出：[[2,3,4],[4,5]]

用例2：

• 输入：target = 15
• 输出：[[1,2,3,4,5],[4,5,6],[7,8]]

思路

双指针模拟滑动窗口，具体可以参考代码实现中的注释

代码实现

var __readline = require("readline-sync");
__readline.setDefaultOptions({ prompt: "" });
var readline = __readline.prompt;

console.log("请输入target: ");
const target = parseInt(readline());

/**
 * @param {number} target
 * @return {number[][]}
 */
var findContinuousSequence = function (target) {
  // 1 2 3 4 5 6 7 8
  // 等差数列求和公式
  // cur = (fast - slow + 1)(fast + slow) / 2

  // 快慢指针模拟滑动窗口
  let res = [];
  let slow = 1;
  let fast = 2;
  let cur = 0;
  while (slow < fast) {
    cur = ((fast - slow + 1) * (fast + slow)) / 2;
    if (cur === target) {
      let temp = [];
      for (let i = slow; i <= fast; i++) {
        temp.push(i);
      }
      res.push(temp);
      slow++;
      fast++;
    } else if (cur <= target) {
      fast++;
    } else {
      slow++;
    }
  }
  return res;
};

const res = findContinuousSequence(target);
console.log("结果为: ", res);

/* 
  请输入target:
  15
  结果为:  [ [ 1, 2, 3, 4, 5 ], [ 4, 5, 6 ], [ 7, 8
  ] ]


  请输入target:
  9
  结果为:  [ [ 2, 3, 4 ], [ 4, 5 ] ]
*/