和为 s 的连续正数序列

解题思路：

  1. 初始化窗口的边界，初始化值为 left = 1、right = 2，窗口的和为 sum = 3；

  2. 当窗口的和小于 target，right 不断右移拓宽窗口的宽度，并维护窗口的值 sum += right；

  3. 当窗口的和大于 target，left 不断右移收缩窗口的宽度，并维护窗口的值 sum -= left；

  4. 优化点：并不需要循环遍历整个 target 长度，只需要循环 target 一半加 1 的长度；

复杂度：

  1. 时间复杂度：由于两个指针移动均单调不减，且最多移动 target/2 次，所以时间复杂度为 O(target)；

  2. 空间复杂度：O(1)；

代码实现：

function findContinuousSequence(target: number): number[][] {
  let res = [];
  if (target <= 2) return res;

  let left = 1;
  let right = 2;
  let sum = 3;

  while (left < right && right <= (target >> 1) + 1) {
    if (sum === target) {
      const temp = [];
      for (let k = left; k <= right; k++) {
        temp.push(k);
      }
      res.push(temp);
    }

    if (sum > target) {
      // 当窗口的和 >= target，左窗口向右收缩
      sum -= left;
      left++
    } else {
      // 当窗口的和 < target，右窗口向右拓宽
      right++;
      sum += right;
    }
  }

  return res;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
评论

中午好👏🏻，我是 ✍🏻   疯狂 codding 中...

粽子

这有关于前端开发的技术文档和你分享。

相信你可以在这里找到对你有用的知识和教程。

了解更多

目录

  1. 1. 和为 s 的连续正数序列
  2. 2. 解题思路：
  3. 3. 复杂度：
  4. 4. 代码实现：