和为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);
}