【牛客网】剑指offer编程题：构建乘积数组

 因为题目规定不能用除法，所以把 B 分成两部分，即前缀部分和后缀部分：

      mul_pre[i] = A[0]*A[1]*....A[i-1]*A[i]；

      mul_suf[i] = A[i]*A[i+1]*...A[n-1];

      B[i] = mul_pre[i-1] * mul_suf[i+1];

代码如下：

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        int n = A.size();
        vector<int> mul_pre(n, 0); //定义前缀
        vector<int> mul_suf(n, 0); //定以后缀
        vector<int> B(n, 0);
        for (int i = 0; i < n; i++)  //计算前缀
        {
            if (i == 0)
                mul_pre[i] = A[i]; //边界
            else 
                mul_pre[i] = mul_pre[i-1] * A[i];
        }
        for (int i = n-1; i >= 0; i--) //计算后缀
        {
            if (i == n-1)
               mul_suf[i] = A[i]; //边界
            else 
               mul_suf[i] = mul_suf[i+1] * A[i];
        }
        for (int i = 0; i < n; i++) //计算B
        {
            if (i == 0)
                B[i] = mul_suf[i+1];
            else if (i == n-1)
                B[i] = mul_pre[i-1];
            else
                B[i] = mul_pre[i-1] * mul_suf[i+1];
        }
        return B;
    }
};