嵌套 for 循环太慢 - PHP Codewars Kata Integers：娱乐一

Question

我正在研究这个 codewars kata 并让它通过了基本测试。但是，最终提交超时。我知道这是一个嵌套的 for 循环，似乎我遇到了 Big O，但不知道如何绕过它。我怎样才能让它更快？

function listSquared($m, $n) {
    $results = [];

    for ($i = $m; $i <= $n; $i++) {

        $squared_divisors = [];

        for ($num = 1; $num <= $i; $num++) {
            if ($i % $num === 0) {
                array_push($squared_divisors, ($num * $num));
            }
        }

        $sum = array_sum($squared_divisors);
        $sqrt_sum = sqrt($sum);

        if ((int)$sqrt_sum == $sqrt_sum) {
            array_push($results, [$i, $sum]);
        }
    }

    return $results;
}

Answer 1

您至少可以节省两项：

• 内部循环可以将

  $num

  识别为

  $i / $num

  作为除数，然后您可以提前退出循环 - 当

  $num

  超过

  $i

  的平方根时

• 您不需要将这些平方除数存储在数组中：您可以立即将它们添加到

  $sum

这导致了这段代码：

function listSquared($m, $n) {
    $results = [];

    for ($i = $m; $i <= $n; $i++) {

        $sum = 0;
        $max = sqrt($i);
        for ($num = 1; $num <= $max; $num++) {
            if ($i % $num === 0) {
                $sum += $num * $num;
                $quot = $i / $num;
                if ($quot > $num) {
                    $sum += $quot * $quot;
                }
            }
        }

        $sqrt_sum = sqrt($sum);

        if ((int)$sqrt_sum == $sqrt_sum) {
            array_push($results, [$i, $sum]);
        }
    }

    return $results;
}