php实现构建排除当前元素的乘积数组方法

1. 问题背景

给定一个整数数组 nums，其中 nums[i] 表示第 i 个数字，要求返回一个数组 ans，其中 ans[i] 等于除 nums[i] 以外的数组元素的乘积。请你不要使用除法，且在 O(n) 时间复杂度内完成此题。你可以假设数组中所有元素的乘积在 32 位有符号整数范围内。

2. 解题思路

2.1 思路概述

首先使用前缀乘积数组 pre 和后缀乘积数组 suf 分别记录每个元素左边的数的乘积和右边的数的乘积，即：

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

    $pre[$i] = $pre[$i - 1] * $nums[$i - 1];
    $suf[$n - $i - 1] = $suf[$n - $i] * $nums[$n - $i];
}

然后遍历 nums，对于第 i 个元素，它的乘积等于 pre[i] 和 suf[i] 的乘积，即：

$ans[$i] = $pre[$i] * $suf[$i];

最后返回 ans 即可。

2.2 代码实现

以下是完整代码实现：

function productExceptSelf($nums) {

    $n = count($nums);
    $pre = array_fill(0, $n, 1);
    $suf = array_fill(0, $n, 1);
    for ($i = 1; $i < $n; ++$i) {
        $pre[$i] = $pre[$i - 1] * $nums[$i - 1];
        $suf[$n - $i - 1] = $suf[$n - $i] * $nums[$n - $i];
    }
    $ans = array_fill(0, $n, 0);
    for ($i = 0; $i < $n; ++$i) {
        $ans[$i] = $pre[$i] * $suf[$i];
    }
    return $ans;
}

3. 总结

本篇文章介绍了如何利用前缀乘积数组和后缀乘积数组来求解乘积数组问题，这是一种非常高效的解题思路。这个思路还可以被运用到其他与求解乘积有关的问题上。