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

心谭博客

发布于 2020-04-21 15:45:31

7410

发布于 2020-04-21 15:45:31

文章被收录于专栏：YuanXin

题目描述：输入一个正整数 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;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-03-26，如有侵权请联系 cloudcommunity@tencent.com 删除

target