【LeetCode】剑指 Offer 66. 构建乘积数组 p312 -- Java Version

题目链接：https://leetcode.cn/problems/gou-jian-cheng-ji-shu-zu-lcof/

1. 题目介绍（66. 构建乘积数组）

给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。

【测试用例】：

【条件约束】：

2. 题解

2.1 乘积矩阵 – O(n) ⭐

时间复杂度O(n)，空间复杂度O(1)

【解题思路】：
除法： 如果没有不能使用除法的限制，我们则可以使用公式 (A[0] * A[1] * ... * A[n-1] ) / A[i] 来求得 B[i]；在使用除法时，只需要注意 A[i] 等于 0 的情况即可。
……
乘积数组：我们可以将 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1] 分成两部分，一部分定义为 C[i] = A[0]×A[1]×...×A[i-1] = C[i-1] ×A[i-1]；另一部分定义为 D[i] = A[i+1]×…×A[n-1] = D[i+1] × A[i+1]。那么我们就得到了 B[i]= C[i] ×D[i]
……
【实现策略】：

1. 首选获取输入数组的长度 len1，进行无效输入的判断；
2. 定义数组 B, 用来存储返回结果；
3. 第一次循环，让 B[i] 累乘为 C[i];
4. 第二次循环，让 B[i] 累乘为 C[i] * D[i]；
5. 最后返回结果。

class Solution {
    // Solution1：B[i] = C[i] * D[i];
    // C[i] = A[0] * ... * A[i-1];
    // D[i] = A[i+1] * ... * A[n-1];
    public int[] constructArr(int[] a) {
        int len1 = a.length;  // 获取数组A的长度
        if (len1 <= 0) return new int[0];  // 无效输入判断
        int[] b = new int[len1];  // 定义数组B，用来存储返回结果

        b[0] = 1;
        for (int i = 1; i < len1; i++) {  // 累乘让 B[i] = C[i]
            b[i] = b[i-1] * a[i-1];
        }

        int temp = 1;
        for (int j = len1-2; j >= 0; j--) {  // 累乘 让 C[i] * D[i]
            temp *= a[j+1];
            b[j] *= temp;
        }

        return b;
    }
}