和为s的两个数字

题目描述

输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

分析

定义两个指针，分别指向数组的头和尾，两个指针都往中间移动。
移动过程中：

• 如果两个指针指向的元素和大于 target，则右指针往左移一位。
• 如果两个指针指向的元素和小于 target，则左指针往右移一位。
• 如果两个指针指向的元素和等于 target，则判断其乘积是否小于结果数组，如果是则放入结果数组。

代码

<?php

namespace app\index\controller;

class Test
{

    /**
     * 输入数据
     */
    public function test()
    {
        $array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20];
        $sum   = 21;
        $res   = $this->FindNumbersWithSum($array, $sum);
        print_r($res);
    }

    /**
     * @title 查找满足条件的两个数
     * @param $array 升序数组
     * @param $sum   两数之和
     * @return array
     */
    function FindNumbersWithSum($array, $sum)
    {
        $l   = 0;                  // 左指针
        $r   = count($array) - 1;  // 右指针
        $res = [];                 // 结果数组

        // 当左右指针不相遇时循环
        while ($l < $r) {
            if ($array[$l] + $array[$r] < $sum) $l++;      // 如果两数之和小于 target
            elseif ($array[$l] + $array[$r] > $sum) $r--;  // 如果两数之和大于 target
            else {
                // 第一次和等于 target 的两数直接放入结果数组
                // 而新的和等于 target，则判断其积是否更小
                if (array_product([$array[$l], $array[$r]]) < array_product($res) || empty($res)) {
                    $res = [$array[$l], $array[$r]];
                }
                $l++;
                $r--;
            }
        }
        return $res;
    }
}

笔记

array_product($array):计算数组元素的乘积。