和为s的连续正数序列

未匹配的标注

题目描述

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

示例

输入:

target = 9

输出:

[[2,3,4],[4,5]]

分析

滑动窗口(即框住数组一段连续的元素)从数组最左边开始滑动,当滑动窗口的右边抵达 target 值的一半时,停止查找。

在滑动过程中:

  • 如果窗口内元素总和小于 target,则窗口右边界往右移一位。(扩大窗口)
  • 如果窗口内元素总和大于 target,则窗口左边界往右移一位。(缩小窗口)
  • 如果窗口内元素总和等于 target,则将窗口元素放入结果数组。(找到序列)

代码

<?php

namespace app\index\controller;

class Test
{
    /**
     * 查找满足条件的连续正整数序列
     */
    public function FindContinuousSequence($target)
    {
        $left = $right = 1;                // 滑动窗口的左右边界初始化为 1
        $sum  = 0;                         // 滑动窗口内的所有元素总值
        $end  = ceil($target / 2) + 1;     // 窗口的右边界最大到 target 值的一半
        $res  = [];                        // 存放所有满足条件的序列

        while ($right <= $end ) {
            // 如果窗口内总值小于目标值,则计入总值,并右边界右移
            if ($sum < $target) {
                $sum = $sum + $right;
                $right++;
            } elseif ($sum > $target) {
                // 如果窗口总值大于目标值,则从总值中减去,并左边界右移
                $sum = $sum - $left;
                $left++;
            } else {
                // 如果窗口总值等于目标值,则放入结果数组,继续移动
                $tmp = [];  // 存放每一次的连续序列
                for ($i = $left; $i < $right; $i++) $tmp[] = $i;
                if(count($tmp)>=2) $res[] = $tmp;  // 保证至少两个数

                $sum   = $sum - $left;
                $left++;
            }
        }
        return $res;
    }
}
/**
* 输入数据
*/
public function test()
{
    $target = 3;
    $res    = $this->FindContinuousSequence($target); // 调用函数
    print_r($res);
}

本文章首发在 LearnKu.com 网站上。

上一篇 下一篇
讨论数量: 0
发起讨论 只看当前版本


暂无话题~