【Hot100】LeetCode—238. 除自身以外数组的乘积

---

• 原题链接：238. 除自身以外数组的乘积

---

1- 思路

前缀和

• 1- 维护 左乘积前缀和 preL 和 右乘积前缀和 preR
  • 左前缀和乘积：从 1 开始遍历，到 nums.length
  • 右前缀和乘积：从 nums.length-1 开始遍历，到 0
• 2. 遍历结果数组
  • res[i] = preL[i] * preR[i]

---

2- 实现

⭐238. 除自身以外数组的乘积——题解思路

class Solution {public int[] productExceptSelf(int[] nums) {int[] res = new int[nums.length];int[] preL = new int[nums.length];int[] preR = new int[nums.length];preL[0] = 1;preR[nums.length-1] = 1;for(int i = 1 ; i < nums.length;i++){preL[i] = preL[i-1] *nums[i-1];}for(int i = nums.length-2 ; i >=0 ;i--){preR[i] = preR[i+1] *nums[i+1];}for(int i = 0 ; i < nums.length;i++){res[i] = preL[i] * preR[i];}return res;}
}

---

3- ACM 实现

public class productExceptSelf {public static int[] product(int[] nums){int[] res = new int[nums.length];int[] preL = new int[nums.length];int[] preR = new int[nums.length];// 求左前缀preL[0] = 1;for(int i = 1;i<nums.length;i++){preL[i] = preL[i-1]*nums[i-1];}preR[nums.length-1] = 1;for(int i = nums.length-2;i>=0;i--){preR[i] = preR[i+1]*nums[i+1];}for(int i = 0 ;i < nums.length;i++){res[i] = preL[i]*preR[i];}return res;}public static void main(String[] args) {System.out.println("输入数组长度");Scanner sc = new Scanner(System.in);int n = sc.nextInt();int[] nums = new int[n];for(int i = 0 ; i < n;i++){nums[i] = sc.nextInt();}int[] res = product(nums);for(int i : res){System.out.print(i+" ");}}
}