题目描述

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

示例 1:

输入: nums = [1,2,3,4]
输出: [24,12,8,6]

题目分析

开两个数组分别存储前缀积和后缀积
时间复杂度 O(n), 空间复杂度 O(n)

进阶：
可以借助 ans 数组实现前缀积的暂存
不考虑 ans 数组的空间，此时空间复杂度为 O(1)

Java

public int[] productExceptSelf1(int[] nums) {
    int n = nums.length;
    int[] left = new int[n];
    int[] right = new int[n];
    int[] ans = new int[n];
    left[0] = nums[0];
    for (int i = 1; i < n; i++) {
        left[i] = nums[i] * left[i - 1];
    }
    right[n - 1] = nums[n - 1];
    for (int i = n - 2; i >= 0; i--) {
        right[i] = nums[i] * right[i + 1];
    }
    for (int i = 1; i < n - 1; i++) {
        ans[i] = left[i - 1] * right[i + 1];
    }
    ans[0] = right[1];
    ans[n - 1] = left[n - 2];
    return ans;
}

public int[] productExceptSelf2(int[] nums) {
    int n = nums.length;
    int[] ans = new int[n];

    // 前缀积
    ans[0] = 1;
    int temp = 1;
    for (int i = 1; i < n; i++) {
        temp *= nums[i - 1];
        ans[i] = temp;
    }

    // 后缀积
    temp = 1;
    for (int i = n - 2; i >= 0; i--) {
        temp *= nums[i + 1];
        ans[i] *= temp;
    }

    return ans;
}

Kotlin

fun productExceptSelf(nums: IntArray): IntArray {
    val n = nums.size
    val ans = IntArray(n)
    var temp = 1
    ans[0] = 1
    for (i in 1..n - 1) {
        temp *= nums[i - 1]
        ans[i] = temp
    }

    temp = 1
    for (i in n - 2 downTo 0) {
        temp *= nums[i + 1]
        ans[i] *= temp
    }
    return ans
}