题目

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

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

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

示例 1:

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

示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

提示：

• 2 <= nums.length <= 10⁵
• -30 <= nums[i] <= 30
• 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内

解法

解法一 暴力 数组相乘

class Solution {
    public int[] productExceptSelf(int[] nums) {
        // 数组相乘 时间复杂度O(N^2)
        int[] result = new int[nums.length];
        Arrays.fill(result, 1);
        for (int i = 0; i < nums.length; i++) {
            int[] temp = new int[nums.length];
            Arrays.fill(temp, nums[i]);
            temp[i] = 1;
            for (int j = 0; j < nums.length; j++) {
                result[j] *= temp[j];
            }
        }
        return result;
    }
}

时间复杂度是O(N²)，不能通过时间限制

解法二 前缀乘积思想

每个元素除本身元素乘积实际上就是前缀乘积和后缀乘积的乘积。

• 一个遍历得到前缀和数组
• 一个遍历得到后缀和数组
• 得到结果

class Solution {
    public int[] productExceptSelf(int[] nums) {
        // 前缀后缀乘积相乘
        // 1. 前缀乘积数组
        int[] prefix = new int[nums.length], suffix = new int[nums.length], result = new int[nums.length];
        prefix[0] = 1;
        for (int i = 1; i < nums.length; i++) 
            prefix[i] = prefix[i - 1] * nums[i - 1];
        // 2. 后缀乘积数组
        suffix[nums.length - 1] = 1;
        for (int i = nums.length - 2; i >= 0; i--) 
            suffix[i] = suffix[i + 1] * nums[i + 1];
        // 3. 得到结果
        for (int i = 0; i < nums.length; i++) 
            result[i] = prefix[i] * suffix[i];
        
        return result;
    }
}

时间复杂度：O(N)

改进 在遍历前缀和后缀乘积数组的流程中直接计算result

class Solution {
    public int[] productExceptSelf(int[] nums) {
        // 前缀后缀乘积相乘
        // 1. 前缀乘积数组 并 计算result
        int[] result = new int[nums.length];
        Arrays.fill(result, 1);
        int prefix = 1, suffix = 1;
        for (int i = 0; i < nums.length; i++) {
            result[i] *= prefix;
            prefix *= nums[i];
        } 
        // 2. 后缀乘积数组 并 得到结果
        for (int i = nums.length - 1; i >= 0; i--) {
            result[i] *= suffix;
            suffix *= nums[i];
        }
        return result;
    }
}

省去了 前缀乘积和后缀乘积数组 的存储， 优化了空间复杂度

小结

这道题类似于前缀和的思想

除自身以外数组的乘积 = 前缀乘积 * 后缀乘积