【剑指offer:和为s的连续正数序列】巧用快慢指针

题目描述:输入一个正整数 target ,输出所有和为 target 的连续正整数序列(至少含有两个数)。序列内的数字由小到大排列,不同序列按照首个数字从小到大排列。

示例

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

# 解法:快慢指针

和前面题目很相似,这里也是“双指针”的思路。不同的地方有 2 个点:

  • 指针是从第 0 个和第 1 个位置开始的(下面称为 a 和 b)
  • 这里要计算指针范围内的所有元素和(题目要求是“连续序列”)
  • 每次移动 a、b 之前,都要计算一下当前[a,b]范围内的所有元素和。如果等于 s,打印并且 b 右移;如果小于 s,b 右移;如果大于 s,a 右移。

至于为什么相等的时候 b 右移而不是 a 右移?因为 b 右移后,可能发生 a 右移。但是如果 a 直接右移,那么会漏掉情况。

代码实现如下:

// ac地址:https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/
// 原文地址:https://xxoo521.com/2020-03-26-find-sub-sequence/

/**
 * @param {number} target
 * @return {number[][]}
 */
var findContinuousSequence = function (target) {
  let a = 1,
    b = 2,
    sum = a + b;
  const res = [];
  while (a !== b && b <= target) {
    if (sum === target) {
      res.push(getSubSequence(a, b));
      ++b;
      sum += b;
    } else if (sum > target) {
      sum -= a; // 注意,这里是先减去指针对应的值,再移动指针
      ++a;
    } else {
      ++b;
      sum += b;
    }
  }
  return res;
};

function getSubSequence(start, end) {
  const res = [];
  for (let i = start; i <= end; ++i) {
    res.push(i);
  }
  return res;
}

# 更多资料

整理不易,若对您有帮助,请给个「关注+点赞」,您的支持是我更新的动力 👇