238. 除自身以外数组的乘积

Problem: 238. 除自身以外数组的乘积

思路

在不能使用除法的情况下，考虑每个答案的组成方式：第i位的结果为其前缀乘积和后缀乘积之积。离线求解前后缀乘积时间复杂度为$O(n)$，符合题目要求。

题目中给了个提示，可以在$O(1)$（不考虑返回数组）的情况下完成。但是完全不存储前后缀是没法在$O(n)$的复杂度下完成的，应该想到可以暂时把数据存在返回数组里。

这样，我们只需先计算一遍后缀积，然后在计算结果时，保留当前前缀和即可。

复杂度

• 时间复杂度: $O(n)$：遍历两次数组。
• 空间复杂度: $O(1)$：实际上是$O(n)$，如题目所说不考虑返回数组空间时$O(1)$。

Code

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int r[] = new int[n];
        r[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            r[i] = r[i + 1] * nums[i];
        }
        r[0] = r[1];
        int pre = nums[0];
        for (int i = 1; i < n - 1; i++) {
            r[i] = pre * r[i + 1];
            pre *= nums[i];
        }
        r[n - 1] = pre;
        return r;
    }
}