图解LeetCode——238. 除自身以外数组的乘积

一、题目

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

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

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

二、示例

2.1> 示例 1:

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

2.2> 示例 2:

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

提示：

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

三、解题思路

根据题目要求，我们需要计算出数组nums中，每个元素除自己之外的乘积值，即假设nums包含4个元素，分别为nums[0]~`nums[3]`，那么最终结果如下所示：

nums[0] = nums[1] * nums[2] * nums[3]； nums[1] = nums[0] * nums[2] * nums[3]； nums[2] = nums[0] * nums[1] * nums[3]； nums[3] = nums[0] * nums[1] * nums[2]；

但是如果按照上面计算我们会发现一个问题，就是会出现很多重复计算，比如我们计算nums[0]和nums[1]的时候，针对nums[2] * nums[3]这部分就是重复计算的。所以，为了解决这个问题，我们可以看下面这个图，在这个图中白色的格子表示不参与计算，那么正好可以分割为左下角和右上角两部分数字集合，具体情况请见下图所述：

针对上面的分析，我们可以分为两部分对数组nums进行计算操作：

【正向遍历数组】 这种遍历方式，我们可以来计算左下角的数字乘积； 【逆向遍历数组】 这种遍历方式，我们可以来计算右上角的数字乘积（用temp保存），然后与左下角再执行相乘操作；

好了，如上就是本题的解题思路了，为了便于大家理解，我们以nums = [1,2,3,4]为例，看一下具体的操作过程。请见下图所示：

四、代码实现

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

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

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