PHP实现Codewars的Integers: Recreation One算法超时优化求助

问题描述 #

数字246的因数为1、246、2、123、3、82、6、41。将这些因数平方后得到：1、60516、4、15129、9、6724、36、1681。这些平方数的和为84100，而84100恰好是290的平方。

任务 #

找出m到n之间（1 ≤ m ≤ n，m和n为整数）所有满足「其因数平方和本身是平方数」的整数。返回一个包含子数组的数组，每个子数组包含两个元素：第一个是符合条件的整数，第二个是其因数平方和。

示例 #

list_squared(1, 250) → [[1, 1], [42, 2500], [246, 84100]]
list_squared(42, 250) → [[42, 2500], [246, 84100]]

问题与原始代码 #

我的代码能通过基础测试，但提交时超时。我知道嵌套for循环导致时间复杂度太差，但不知道怎么改。请问如何优化代码提升速度？

原始代码：

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;
}

优化方案 #

核心优化思路 #

原始代码的内层循环遍历到$i，时间复杂度为O(n²)，这是超时的根本原因。优化方向集中在减少因数查找的遍历范围和降低不必要的操作开销。

1. 缩小因数查找范围

找因数无需遍历到$i，只需遍历到sqrt($i)即可：

• 若num是$i的因数，则$i / num也必然是$i的因数
• 这样内层循环的时间复杂度从O(n)降至O(√n)，整体效率大幅提升

2. 直接累加平方和，避免数组操作

不需要将所有因数平方值存入数组再求和，直接在遍历过程中累加，减少数组的创建、插入和求和开销。

3. 避免平方根重复计算

提前计算sqrt($i)并赋值给变量，避免循环中重复调用sqrt()函数。

优化后的代码 #

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

    for ($i = $m; $i <= $n; $i++) {
        $sum = 0;
        $sqrtI = sqrt($i);
        
        for ($num = 1; $num <= $sqrtI; $num++) {
            if ($i % $num === 0) {
                $sum += $num * $num;
                $pair = $i / $num;
                // 当因数是平方根时，避免重复累加（如4的因数2，只加一次平方）
                if ($pair !== $num) {
                    $sum += $pair * $pair;
                }
            }
        }

        $sqrtSum = sqrt($sum);
        if ((int)$sqrtSum === $sqrtSum) {
            $results[] = [$i, $sum];
        }
    }

    return $results;
}

额外优化建议 #

如果函数会被多次调用，或者处理范围存在重复数值，可以添加缓存机制（比如用静态数组存储已计算过的数的平方和），避免重复计算，进一步提升效率。

内容的提问来源于stack exchange，提问作者Ryan M