CodingInterview-构建乘积数组

参考了书中的思路，解法非常巧妙。将乘法分为两半，一半是A[0]*A[1]*...*A[i-1]，另一半是A[i+1]*A[i+2]*...*A[n-1]。这两半可以分别从左边和右边算起。从左边开始算的时候，只要保证result[i]是它的前一个值和 A 的前一个值相乘即可。而从右边算起的时候，只要保证是后一个值得累乘就可以了。

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        vector<int> result;
        int length=A.size();
        if(length<=0) return result;
        result.push_back(1);
        for(int i=1;i<length;i++){
            result.push_back(result[i-1]*A[i-1]);
        }
        int temp=1;
        for(int i=length-1;i>=0;i--){
            result[i]*=temp;
            temp*=A[i];
        }
        return result;
    }
};