大厂面试题练习-所有和为N的连续正数序列

题目：求所有和为 N 的连续正数序列

示例

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

答案

解题思路

1. 首先根据输入值 N 求出数列的中间值，大于数列中间值的那一部分可以不用考虑了，因为大于数列中间值那部分任意两个数相加都大于 N，所以我们只需要在小于等于 Math.fllor(N/2)的数列里面找就可以
2. 从数列的第 i(i=1) 项开始找，累加每一项的值之后进行判断，如果当前累加的数大于 N 则重新从数列第 i+1 项开始查找；如果小于 N，则继续累加下一项；如果等于 N，假设一共累加了 j 项，则将第 i 项及后面的 j 项值存起来；然后继续从 i+1 项开始查找，直到 i 大于第一步所求的中间值而已；

代码

function createArr(n, len) {
  let arr = new Array(len).fill(null),
    temp = [];
  arr[0] = n;
  arr = arr.map((item, index) => {
    if (item === null) {
      item = temp[index - 1] + 1;
    }
    temp.push(item);
    return item;
  });
  return arr;
}
function findMaxLenSequence(num) {
  let res = [];
  // 外层循环的最大索引
  const middle = Math.floor(num / 2);
  //从1开始累加
  for (let i = 1; i <= middle; i++) {
    //控制累加多少次,假设从i开始加起，一共加j项
    for (let j = 2; ; j++) {
      //求出累加多次的和
      let sum = ((2 * i + j - 1) * j) / 2;
      if (sum > num) {
        break;
      } else if (sum === num) {
        res.push(createArr(i, j));
        break;
      }
    }
  }
  return res;
}
console.log(findMaxLenSequence(15));
// [ [ 1, 2, 3, 4, 5 ], [ 4, 5, 6 ], [ 7, 8 ] ]