题解 | #构建乘积数组#

第七十七题

处理保存 该点的左右两边的乘积

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        // 不能用除法 所以不能全部乘完再一个个除
        // 方法一 两次循环 每一个点单独求，显然不是想要的算法
        // 求出left right 两个数组，每次计算该点两边数组的乘积即可
        vector<int>left;
        vector<int>right;
        // 计算左右两边累乘的结果
        // 初始化 就是第一个
        left.push_back(A[0]);
        right.push_back(A[A.size()-1]);
        // 遍历保存左右两边的乘积
        for(int i=1;i<A.size()-1;i++)
        {
            left.push_back(left[i-1]*A[i]);
            right.push_back(right[i-1] * A[A.size()-i-1] );
        }
        vector<int> retans;
        
        // 左右两个边累乘结果输出
        /*
        for(int i=0;i<A.size()-1;i++)
        {
            cout<<left[i]<<" ";
        }
        cout<<endl;

        for(int i=0;i<A.size()-1;i++)
        {
            cout<<right[i]<<" ";
        }
        cout<<endl;
        */
        
        // 计算返回的结果
        for(int i=0;i<A.size();i++)
        {
            // 分别取该点的左边所有累乘的结果 * 该点右边累乘的结果
            // cout<<left[i-1]<<" "<<right[right.size()-i-1]<<endl;
            retans.push_back(left[i-1]*right[right.size()-i-1]);
        }
        // 修改第一个 和最后一个
        retans[0]=right[right.size()-1];
        retans[A.size()-1]=left[left.size()-1];
        return retans;
    }
};