剑指 Offer 66. 构建乘积数组

image.png

题目：求除了自己的其余元素的乘积
首先建立下图这样一个矩阵：
一共有n列nums【0~n-1】
只不过对角线变为1，代表不乘自己
我们要做的是什么？把除了对角线的元素都乘起来，相当于先对每行，先乘左下角的元素，再乘右下角的元素

image.png

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n=nums.length;
        if(n==0) return new int[0];
        int temp=1;
        int [] res=new int[n];
        res[0]=1;//初始化
        for(int i=1;i<n;i++){//把第i个元素的左边元素先乘起来
            res[i]=res[i-1]*nums[i-1];
        }
        for(int j=n-2;j>=0;j--){
           temp=temp*nums[j+1];//把第i个元素的右边元素乘起来，temp会保留之前的元素
           res[j]=res[j]*temp;//和左边的元素乘起来
        }
   return res;
    }
}