普通数组-238. 除了自身以外数组的乘积（数组、前缀和）

挺简单的

一、核心解题思路

1. 前缀积数组prefix：prefix[i]表示nums[0..i-1]所有元素的乘积（即i位置左边所有元素的乘积）
2. 后缀积数组suffix：suffix[i]表示nums[i+1..n-1]所有元素的乘积（即i位置右边所有元素的乘积）
3. 结果数组answer：answer[i] = prefix[i] * suffix[i]，即左右两边乘积的组合，完美避开除法，时间复杂度 O (n)，空间复杂度 O (n)

classSolution{publicint[]productExceptSelf(int[]nums){intn=nums.length;int[]prefix=newint[n];prefix[0]=1;for(inti=1;i<n;i++){prefix[i]=prefix[i-1]*nums[i-1];}int[]postfix=newint[n];postfix[n-1]=1;for(inti=n-2;i>=0;i--){postfix[i]=postfix[i+1]*nums[i+1];}int[]res=newint[n];for(inti=0;i<n;i++){res[i]=prefix[i]*postfix[i];}returnres;}}

二、完整可运行代码（大厂机考版）

importjava.util.Scanner;publicclassMain{publicstaticint[]productExceptSelf(int[]nums){intn=nums.length;// 1. 初始化前缀积数组：prefix[i] = nums[0] * nums[1] * ... * nums[i-1]int[]prefix=newint[n];prefix[0]=1;// 第一个元素左边没有元素，乘积为1for(inti=1;i<n;i++){prefix[i]=prefix[i-1]*nums[i-1];}// 2. 初始化后缀积数组：postfix[i] = nums[i+1] * nums[i+2] * ... * nums[n-1]int[]postfix=newint[n];postfix[n-1]=1;// 最后一个元素右边没有元素，乘积为1for(inti=n-2;i>=0;i--){postfix[i]=postfix[i+1]*nums[i+1];}// 3. 计算最终结果：左右乘积相乘int[]res=newint[n];for(inti=0;i<n;i++){res[i]=prefix[i]*postfix[i];}returnres;}publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);// 读取数组长度intn=sc.nextInt();int[]nums=newint[n];// 读取数组元素for(inti=0;i<n;i++){nums[i]=sc.nextInt();}// 输出结果for(inti:productExceptSelf(nums)){System.out.print(i+" ");}}}