[leetcode/lintcode 题解] 国内大厂面试高频题： 数组除了自身的乘积

描述
给定n个整数的数组nums，其中n> 1，返回一个数组输出，使得output [i]等于nums的所有除了nums [i]的元素的乘积。
在没有除和O(n)时间内解决

在线评测地址：领扣题库官网

样例1
输入: [1,2,3,4]
输出: [24,12,8,6]
解释:
2*3*4=24
1*3*4=12
1*2*4=8
1*2*3=6

样例2
输入: [2,3,8]
输出: [24,16,6]
解释:
3*8=24
2*8=16
2*3=6

解题思路
如果暴力计算每个位置的答案值的话，时间会达到O(N^2)。
如果先将所有数乘起来，每个位置除以当前的数，有可能会整型溢出。
观察可以发现，每个数其实就是它前面部分的积乘以后面部分的积。所有前缀的积，通过一次遍历即可算出来，后缀也是一样。我们可以边乘边算前缀积，同时将他乘在结果数组上，这样达到了O(1)的额外空间，同时不用到除法。
代码思路

1. 令result为一个全是1的数组。
2. 令前缀积prefixProduct等于1，后缀积postfixProduct等于1。
3. 正序遍历数组nums，第i个位置先将结果乘上prefixProduct，再将prefixProduct乘上nums[i]。
4. 逆序遍历数组nums，第i个位置先将结果乘上postfixProduct，再将postfixProduct乘上nums[i]。
5. 返回result。

复杂度分析
设数组长度为N。
时间复杂度

• 遍历两次数组，时间复杂度为O(N)。

空间复杂度

• 只需额外O(1)的时间，记录前缀积和后缀积。

源代码

public class Solution {
    /**
     * @param nums: an array of integers
     * @return: the product of all the elements of nums except nums[i].
     */
    public int[] productExceptSelf(int[] nums) {
        int[] result = new int[nums.length];
        int prefixProduct = 1, postfixProduct = 1;
        
        for (int i = 0; i < result.length; i++) {
            result[i] = 1;
        }
        
        // 将第 i 个位置乘上前 i - 1 个数的积
        for (int i = 0; i < result.length; i++) {
            result[i] *= prefixProduct;
            prefixProduct *= nums[i];
        }
        
        // 将第 i 个位置乘上后面数的积
        for (int i = result.length - 1; i >= 0; i--) {
            result[i] *= postfixProduct;
            postfixProduct *= nums[i];
        }
        
        return result;
    }
}

更多题解参考：九章官网solution