剑指 构建乘积数组

对于每一个B[i]值都分为左右两段的乘积，分别循环得到他们的结果。 O(n^2)

class Solution:
    def multiply(self, A):
        # write code here
        if len(A)==1:
            return -1
        length=len(A)


        B=[0 for _ in range(length) ]
        def multi_result(start,end):
            result=1
            if start>=length:
                return 1
            for i in range(start,end):
                result*=A[i]
            return result
        for i in range(length):
            front=multi_result(0, i)
            later=multi_result(i+1,length)
            B[i]=front*later

        return B

分析，将B[i]的结果分为左右，发现左右分别与其上一个结果有关，所以每次不用重复遍历，只需乘上当前的数值就行，所以从下三角到上三角遍历两次，最终得到结果。

# -*- coding:utf-8 -*-
class Solution:
    def multiply(self, A):
        # write code here
        if len(A)==0:
            return -1
        B=[1 for _ in range(len(A))]
        temp=[1 for _ in range(len(A))]
        temp_=[1 for _ in range(len(A))]
        for i in range(1,len(A)):
           temp[i]=temp[i-1]*A[i-1]
           B[i]*=temp[i]


        for i in range(len(A)-2,-1,-1):
            temp_[i]=temp_[i+1]*A[i+1]
            B[i]*=temp_[i]

        return B