时间戳

首页 > 解决方案 > for循环的PHP超时问题

php - for循环的PHP超时问题

问题描述

我正在尝试解决 PHP 问题，而我整理的内容在某些情况下确实有效，但是对于较大的值和数据集，它会因超时而失败。我需要帮助确定可以做些什么来解决这个问题。

我正在努力进一步发展我的 PHP 知识，这个问题来自我一直在使用的一个测试站点。问题本质上是有两个人加起来可以花在冰淇淋上的钱。有一个风味数组 $cost，每个都由一个整数表示，该整数是风味的成本。需要找到完全等于 $money 金额的两种口味，并显示这两个数字，不是成本，而是口味的数量。问题总是有唯一的解决方案。

我已经过滤了，所以那些花费超过自己的钱的口味甚至都没有得到检查......并且在找到解决方案后检查停止。

<?php 

function whatFlavors($cost, $money) {
    $num_flavors = count($cost);
    $select_flavors = array(0);

    for ($i = 0; $i < $num_flavors; $i++) {
        if (($cost[$i] < $money) && ($select_flavors[0] == '0')) {
            for ($j = 1; $j < $num_flavors; $j++) {
                if ($cost[$j] < $money) {
                    if ($cost[$i] + $cost[$j] == $money) {
                        $select_flavors[0] = $i+1;
                        $select_flavors[1] = $j+1;
                        break;
                    } else {
                        $break;
                    }
                }
            }
        }
    }
    sort($select_flavors);
    echo $select_flavors[0]." ".$select_flavors[1]."\n";

}
?>

要使用测试用例运行代码，请使用：

$stdin = fopen("php://stdin", "r");

fscanf($stdin, "%d\n", $t);

for ($t_itr = 0; $t_itr < $t; $t_itr++) {
    fscanf($stdin, "%d\n", $money);

    fscanf($stdin, "%d\n", $n);

    fscanf($stdin, "%[^\n]", $cost_temp);

    $cost = array_map('intval', preg_split('/ /', $cost_temp, -1, PREG_SPLIT_NO_EMPTY));

    whatFlavors($cost, $money);
}

fclose($stdin);

测试输入详细信息： - 第一行是包含多少测试 - 第二行是要花多少钱 - 第三行是包含多少口味 - 第四行是一个空格分隔的口味数组，每个都由它们的成本表示

有效的示例测试用例：

2 4 5 1 4 5 3 2 4 4 2 2 4 3

超时的测试用例：

由测试站点提供，此处粘贴太长，因此您可以从此链接获取文本文件... https://app.box.com/s/ka01xpigqmvcjflcv0bl9760svdb78vd

标签： php

解决方案

所以你正在寻找加起来达到一定数量的两个数组元素？您在数组中的每个元素上呈指数循环，因此难怪您会遇到超时。

您只需要一个循环即可遍历数组。在每次迭代中，简单的减法都会告诉您您正在寻找什么值。只需使用标准array_search来寻找它。一旦你找到一对，你就可以停止寻找。

<?php

function whatFlavours($cost, $money) {
    foreach ($cost as $i=>$v) {
        $j = array_search($money - $v, $cost);
        if ($j !== false) {
            return [$i, $j];
        }
    }
    return [0, 0];
}

$cost = [23, 53, 13, 46, 11, 8, 27, 4];
$money = 24;
$result = whatFlavours($cost, $money);
echo "$result[0] $result[1]";

输出：

2 4

即 13 + 11。

此外，您永远不应该echo使用函数。始终返回一个值以在函数外使用。

推荐阅读