除自身以外数组的乘积

题目要求

给定一个整数数组nums，要求构造一个新的数组answer。对于answer中的每个元素answer[i]，其值应该是数组nums中除了nums[i]之外所有元素的乘积。题目的限制条件包括：

不可以使用除法操作。
必须在 O(n)的时间复杂度内解决问题。
题目保证所有元素的前缀乘积和后缀乘积都不会超过 32 位整数的范围。

解题思路

要在不使用除法的前提下求解这个问题，可以通过以下步骤来构造answer数组：

初始化两个数组：创建两个数组left和right，其中left[i]用于存储nums[i]左侧所有元素的乘积，right[i]用于存储nums[i]右侧所有元素的乘积。
计算前缀乘积：从左到右遍历nums数组，计算每个元素的前缀乘积并存储在left数组中。left[0]应该初始化为 1，因为第一个元素的左侧没有其他元素。对于left[i]（i > 0），它应该等于left[i - 1] * nums[i - 1]。
计算后缀乘积：从右到左遍历nums数组，计算每个元素的后缀乘积并存储在right数组中。right[n - 1]（其中 n 是nums数组的长度）应该初始化为 1，因为最后一个元素的右侧没有其他元素。对于right[i]（i < n - 1），它应该等于right[i + 1] * nums[i + 1]。
构造答案数组：遍历nums数组，对于每个i，answer[i]应该是left[i]和right[i]的乘积，因为这两个值分别代表了nums[i]左侧和右侧所有元素的乘积。
优化空间复杂度：注意到在构造答案时，实际上不需要同时保留left和right两个数组。可以只使用一个answer数组，并用一个变量来动态地计算后缀乘积。首先利用answer数组按照left数组的构造方法计算前缀乘积，然后再从右向左遍历一次，用一个变量R来代表从右侧开始的累积乘积，并更新answer[i] = answer[i] * R，同时更新R = R * nums[i]。

通过上述步骤，可以在不使用除法且时间复杂度为 O(n)的情况下解决这个问题。

Golang 版本

func productExceptSelf(nums []int) []int {
    length := len(nums)
    // 初始化answer数组，用于存储结果
    answer := make([]int, length)

    // answer[i]先存储索引i左侧所有元素的乘积
    answer[0] = 1
    for i := 1; i < length; i++ {
        answer[i] = nums[i-1] * answer[i-1]
    }

    // R用于存储从右侧开始的累积乘积
    R := 1
    for i := length - 1; i >= 0; i-- {
        // 对于索引i，左侧的乘积已经在answer[i]中，乘以右侧的乘积R
        answer[i] *= R
        // 更新R，包括当前元素nums[i]
        R *= nums[i]
    }

    return answer
}

这段代码实现了上述解题思路，首先计算了每个索引左侧所有元素的乘积，然后从数组的右侧开始遍历，计算右侧所有元素的乘积，并更新结果数组。这样就在 O(n)时间复杂度内，不使用除法，得到了最终的答案数组。

C++版本

#include <vector>

std::vector<int> productExceptSelf(std::vector<int>& nums) {
    int length = nums.size();
    std::vector<int> answer(length, 1);

    // 计算左侧所有元素的乘积
    for (int i = 1; i < length; i++) {
        answer[i] = answer[i - 1] * nums[i - 1];
    }

    // R用于存储从右侧开始的累积乘积
    int R = 1;
    for (int i = length - 1; i >= 0; i--) {
        // 对于索引i，左侧的乘积已经在answer[i]中，乘以右侧的乘积R
        answer[i] *= R;
        // 更新R，包括当前元素nums[i]
        R *= nums[i];
    }

    return answer;
}

这段 C++代码遵循了之前描述的解题思路，首先通过一个循环计算了数组中每个元素左侧所有元素的乘积，然后在第二个循环中从数组的末尾开始，计算右侧所有元素的乘积并更新答案数组。这样就在不使用除法的情况下，以 O(n)的时间复杂度解决了问题。

Python 版本

def productExceptSelf(nums):
    length = len(nums)
    answer = [1] * length

    # 计算左侧所有元素的乘积
    for i in range(1, length):
        answer[i] = answer[i - 1] * nums[i - 1]

    # R用于存储从右侧开始的累积乘积
    R = 1
    for i in reversed(range(length)):
        # 对于索引i，左侧的乘积已经在answer[i]中，乘以右侧的乘积R
        answer[i] *= R
        # 更新R，包括当前元素nums[i]
        R *= nums[i]

    return answer

这段 Python 代码实现了之前描述的算法，首先创建了一个与输入数组等长的答案数组，并初始化所有元素为 1。然后通过两次遍历，一次计算左侧所有元素的乘积，一次计算右侧所有元素的乘积并更新答案数组，从而得到最终结果。

Java 版本

public class Solution {
    public int[] productExceptSelf(int[] nums) {
        int length = nums.length;
        int[] answer = new int[length];

        // 计算左侧所有元素的乘积
        answer[0] = 1;
        for (int i = 1; i < length; i++) {
            answer[i] = answer[i - 1] * nums[i - 1];
        }

        // R用于存储从右侧开始的累积乘积
        int R = 1;
        for (int i = length - 1; i >= 0; i--) {
            // 对于索引i，左侧的乘积已经在answer[i]中，乘以右侧的乘积R
            answer[i] = answer[i] * R;
            // 更新R，包括当前元素nums[i]
            R = R * nums[i];
        }

        return answer;
    }
}

这段 Java 代码遵循了之前描述的算法逻辑，首先初始化一个答案数组，并设置第一个元素的左侧乘积为 1。然后通过两次遍历数组，一次计算左侧所有元素的乘积，一次从右侧开始计算右侧所有元素的乘积并更新答案数组。这样就在不使用除法的情况下，以 O(n)的时间复杂度解决了问题。

Rust 版本

fn product_except_self(nums: Vec<i32>) -> Vec<i32> {
    let length = nums.len();
    let mut answer: Vec<i32> = vec![1; length];

    // 计算左侧所有元素的乘积
    for i in 1..length {
        answer[i] = answer[i - 1] * nums[i - 1];
    }

    // R用于存储从右侧开始的累积乘积
    let mut R = 1;
    for i in (0..length).rev() {
        // 对于索引i，左侧的乘积已经在answer[i]中，乘以右侧的乘积R
        answer[i] *= R;
        // 更新R，包括当前元素nums[i]
        R *= nums[i];
    }

    answer
}

fn main() {
    let nums = vec![1, 2, 3, 4];
    let result = product_except_self(nums);
    println!("{:?}", result);
}

这段 Rust 代码实现了之前描述的算法，首先创建了一个与输入向量等长的答案向量，并初始化所有元素为 1。然后通过两次遍历，一次计算左侧所有元素的乘积，一次计算右侧所有元素的乘积并更新答案向量，从而得到最终结果。在main函数中，我们创建了一个示例向量，并打印了调用product_except_self函数的结果。

总结

这个问题要求我们对于给定的整数数组nums，生成一个新的数组answer，其中每个answer[i]是除了nums[i]之外所有元素的乘积。解决这个问题的关键是不使用除法，并且在 O(n)的时间复杂度内完成。

解题思路分为以下几个步骤：

初始化一个结果数组answer，并将其所有元素设为 1，这样不会影响乘积的计算。
从左到右遍历数组nums，计算每个位置左侧所有元素的乘积，存储在answer数组相应位置。
从右到左遍历数组nums，计算每个位置右侧所有元素的乘积。为了不使用额外的空间，我们用一个变量R来跟踪右侧元素的乘积，并且在遍历的过程中更新answer[i]为answer[i] * R。
在第二次遍历结束后，answer数组中的每个元素就是除了nums[i]之外所有元素的乘积。

这种方法的优点是只需要 O(n)的时间复杂度和 O(1)的空间复杂度（不计算输出数组所占用的空间）。通过两次遍历数组，我们能够得到每个元素左侧和右侧元素的乘积，从而得到最终的答案数组。

hot-100