构建乘积数组

题目：

给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。不能使用除法。

思考：

既然不能用除法，那么就不能先算出A[0] - A[n - 1]的乘积，再除以 i 对应的A[i]的值。

那么，我们可以分两步来求出数组B中的B[i]对应的值。

1、先算出A[0] - A[i - 1]的乘积，放入数组B中。

即先算出B[i] = A[0] * A[1] * A[2] * ... A[i - 1]

在这一部分，存在B[i] = B[i - 1] * A[i - 1](n > 0); 其中，令B[0] = 1;

2、在上一步的基础上，再算B[i] *= B[i + 1] * B[i + 2] * ... B[n - 1];

在这一步中

B[n - 1] *= 1;

B[n - 2] *= A[n -1];

B[n -3] *= A[n - 2] * A[n - 1];

B[n - 4] *= A[n - 3] * A[n - 2] * A[n - 1];

......

B[0] *= A[1] * A[2] * ... A[n - 3] * A[n - 2] * A[n - 1];

不难发现，从n - 1到 0, 所乘上的值 t 满足， t(i) = t(i + 1) * A[i + 1];

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        int len = A.size();
        vector<int> B(len);
        if(len == 0) return B;
        B[0] = 1;
        for(int i = 1; i < len; i++) {
            B[i] = B[i - 1] * A[i - 1];
        }
        int t = 1;
        for(int i = len - 2; i >= 0; i--) {
            t *= A[i + 1];
            B[i] *= t;
        }
        return B;
    }
};