题解 | #构建乘积数组#的Python解法

1.思路

前提
一开始掌柜拿到这题的时候还是有点懵逼的，后来一看示例就开始懂了。题目的三句话需要注意后面这两句话：
- “不能使用除法。”
  有朋友肯定会疑问？为何不可用除法？
  因为你去看示例后就知道，如果是除法，直接这题就变成B[i] = (A[0] * A[1] * ... *A[n-1]) / A[i] *, 就可以直接得到数组B里面的每个元素值！
- “（注意：规定B[0] = A[1] * A[2] * ... * A[n-1]，B[n-1] = A[0] * A[1] * ... * A[n-2];）
  对于A长度为1的情况，B无意义，故而无法构建，因此该情况不会存在。”
  这句又表明：A的长度一定是大于等于2的，翻译为代码就是：len(A) >= 2 AND len(A) <> [] 。
图解示例：
- 首先拆解示例中每个元素值的构成如下图所示（有背景色的才是使用到的元素）：
  
  我们把这个表格分解图再次变换如下👇：
  
  发现规律没？第二个表格以对角线来划分整个B数组，每一行B[i] = B[left] * B[right] （黄色代表左半边乘积；蓝色代表右半边乘积。）
- 接下来再依次查看B[left]和 B[right]两部分乘积的构成：
  - 先看B[left]每一行的乘积：
    
    由上图蓝色框替换红色框的表达式，可以发现从B[1]开始，每一个B[i]都是由上一个B[i-1]乘以每一行A[i-1]得到的。由此可以推理出B[left]的表达式为👉B_left[i] = B[i-1] * A[i-1]。
  - 同理发现每一行B_right[i]就是A[i+1]的乘积,只不过这次是先从最大索引开始逆向走回最小索引，而B_right[4]类似于左半边的B[0]，故定义初始值为1，像下面这样：
    
    即 B_right[i] *= A[i+1], right的每一行对应的A[i+1]乘积。

2.核心代码

# -*- coding:utf-8 -*-
class Solution:
    def multiply(self, A):
        B, right = [1]*len(A), 1 #先定义B数组长度和右边初始值=1
        #看左边的乘积
        for i in range(1, len(A)): #索引起始位是从1开始的
            B[i] = B[i -1] * A [i -1]
        #再看右边
        for i in range((len(A) -2), -1, -1):  #range(start, end, step)这里表示i 从最大索引开始，每次取值减1.
            right *= A[i+1] # 右边的乘积
            B[i] *= right   # 更新B[i] = B[左边] * B[右边]
        return B

最后提交后的得到
图片说明

3. 复杂度分析

时间复杂度：O(n)（遍历数组两次，时间复杂度为2n，常数2可略，所以为O（n），这里n为数组长度）
空间复杂度：O(n)。（遍历数组的大小）

------------------------------------------------我是解法二的分割线---------------------------------------------

4.解法二

4.1 思路

此题其实还有一种思路，就是仔细观察你可以发现每个B[i]的值都是除了对应A[i]值以外的其他元素值的乘积，像下图这样👇：
图片说明
所以可以分别求出以自身为分界线的前面乘积，后面乘积来相乘，即是该B[i]的值。

4.2 核心代码

# -*- coding:utf-8 -*-
class Solution:
    def multiply(self, A):
        B = [1]*len(A)
        left = 1
        right = 1

        for i in range(len(A)):
            B[i] *= left
            B[len(A) - i - 1] *= right  #len(A) - i - 1 表示数组B除开左边和对应自身数值后剩余的即后面的索引位置。
            left *= A[i]                #因为起始位是从0开始，所以left就等于A[i]的乘积。
            right *= A[len(A) - i -1]

        return B

4.3 复杂度分析

时间复杂度：O(n)（遍历数组，n为数组长度）
空间复杂度：O(n)（遍历数组的大小）