图解LeetCode——剑指 Offer 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.1> 示例:

【输入】 [1,2,3,4,5]

【输出】 [120,60,40,30,24]

提示：

• 所有元素乘积之和不会溢出 32 位整数
• a.length <= 100000

三、解题思路

根据这道题的描述，我们其实很容易就想到，现遍历数组中所有的元素，然后针对每个元素执行乘法操作，得到最终的结果之后，如果需要获得B[i]的值，只需要将总的结果除以A[i]即可。但是，本道题已经指明了不能使用除法，那么上面我们最容易想出来的解决方案就不能使用了。

那么还有什么解决办法吗？我们以A[1,2,3,4,5]为例，如果要组成B数组，需要如下方式计算（其中“口”表示略过不计算）:

B[0] = 口  *  2 * 3 * 4 * 5

B[1] = 1 * 口 * 3 * 4 * 5

B[2] = 1 * 2 * 口 * 4 * 5

B[3] = 1 * 2 * 3 * 口 * 5

B[4] = 1 * 2 * 3 * 4 * 口

那么根据上面从B[0]~B[4]的计算公式可以看出来，整个“计算矩阵”是被口分割为两个三角，我们姑且将其称之为“左下角三角”和“右上角三角”。那么针对每个B[i]，我们可以得出如下计算公式，即：B[i] = 左下三角区域[i] ✖️ 右上三角区域[i] 。那么我们执行如下方式执行遍历计算：

【正序遍历】从B[0]开始到B[n-1]，计算的结果是“左下三角形”的值；

【逆序遍历】从B[n-1]开始到B[0]，在计算“右上三角形”值的同时，再乘以左下三角区域[i]的值，那么就是B[i]最终的结果了。

以上就是这道题的解题思路了，下面我们还是举一个例子，这样更方便和深入的让大家理解这道题的解题过程，我们以A数组为{1,2,3,4,5}为例，来看一下计算B数组的过程。请见下图所示：

四、代码实现

class Solution {
    public int[] constructArr(int[] a) {
        int len = a.length;
        if (len == 0) return a;
        int[] result = new int[len];
        result[0] = 1;
        // 计算左下三角的乘积
        for (int i = 1; i < len; i++) 
            result[i] = result[i-1] * a[i-1];
        // 计算右上三角的乘积
        for (int i = len - 2, temp = 1 ; i >= 0; i--) {
            temp *= a[i+1];
            result[i] *= temp;
        }      
        return result;
    }
}

今天的文章内容就这些了：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。

更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享，每天更新」