Codility‘Tape Equilibrium’任务：PHP代码全对却性能0%原因咨询

Hey there! I’ve seen this exact issue a bunch of times with Codility’s Tape Equilibrium problem. The core problem almost always boils down to time complexity—your code works perfectly for small test cases (hence the 100% correctness score), but it can’t handle large input arrays efficiently enough to pass the performance benchmarks.

Let’s break down the most common culprits:

1. You’re recalculating sums from scratch every iteration #

The biggest mistake here is relying on array_sum(array_slice($A, ...)) inside your loop. For example, if your code looks like this:

function solution($A) {
    $minDiff = PHP_INT_MAX;
    $length = count($A);
    for ($i = 0; $i < $length - 1; $i++) {
        $leftTotal = array_sum(array_slice($A, 0, $i + 1));
        $rightTotal = array_sum(array_slice($A, $i + 1));
        $diff = abs($leftTotal - $rightTotal);
        if ($diff < $minDiff) {
            $minDiff = $diff;
        }
    }
    return $minDiff;
}

Each call to array_sum and array_slice takes O(n) time, and you’re repeating this n times. That gives you an overall time complexity of O(n²)—way too slow for large arrays (like the 100,000-element test cases Codility uses for performance checks). The code will time out before finishing, hence the 0% performance score.

2. Unnecessary array operations are killing efficiency #

Even if you’re not recalculating full sums, creating subarrays (with array_slice or similar) adds extra memory overhead and processing time. For big arrays, this leads to high memory usage and slow execution, which also triggers timeouts.

The Fix: Optimize to O(n) Time Complexity #

The correct approach is to calculate the total sum of the array once, then keep a running total of the left side as you iterate. The right side sum is just the total minus the left running total—no need to recalculate anything from scratch. Here’s what that looks like:

function solution($A) {
    $totalSum = array_sum($A);
    $leftSum = 0;
    $minDiff = PHP_INT_MAX;
    $length = count($A);
    
    for ($i = 0; $i < $length - 1; $i++) {
        $leftSum += $A[$i];
        $rightSum = $totalSum - $leftSum;
        $currentDiff = abs($leftSum - $rightSum);
        
        if ($currentDiff < $minDiff) {
            $minDiff = $currentDiff;
        }
    }
    
    return $minDiff;
}

This runs in O(n) time (one pass to calculate the total sum, one pass to iterate through the array) and uses O(1) extra space. It’ll handle even the largest test cases with no issues, giving you 100% performance.

To recap: Your original code works correctly but is too slow for large inputs because it uses an inefficient O(n²) approach. Switching to a running sum method fixes the performance problem entirely.

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