238.除自身以外数组的乘积，前缀和

linwt · linwt · commit 6abae412459f · 2022-04-28T23:04:25.000+08:00
diff --git a/leetcode_Java/DoneTitle.txt b/leetcode_Java/DoneTitle.txt
@@ -94,6 +94,7 @@
 232. 用栈实现队列
 234. 回文链表
 236. 二叉树的最近公共祖先
+238. 除自身以外数组的乘积
 239. 滑动窗口最大值
 240. 搜索二维矩阵 II
 279. 完全平方数
diff --git a/leetcode_Java/DoneType.txt b/leetcode_Java/DoneType.txt
@@ -166,6 +166,7 @@
 136. 只出现一次的数字（哈希表，列表，位运算）
 169. 多数元素（排序，哈希表，投票，计数，分治）
 215. 数组中的第K个最大元素（快速排序，堆排序）
+238. 除自身以外数组的乘积（前缀和）
 239. 滑动窗口最大值（单调递减双端队列）
 240. 搜索二维矩阵 II（二分查找）
 283. 移动零（双指针）
diff --git a/leetcode_Java/Solution0238.java b/leetcode_Java/Solution0238.java
@@ -0,0 +1,29 @@
+// 238. 除自身以外数组的乘积
+
+
+/*
+前缀和：
+1、当前数 = 左边的乘积 x 右边的乘积
+2、初始化结果数组为1，方便乘积时保留左右部分的值
+3、遍历数组，从左到右计算时，当前位置的值为左部分的乘积；从右到左计算时，当前位置的值为右部分的乘积；
+   两次计算都没有将当前位置的值加入乘积，最终当前位置的值就是 左边的乘积 x 右边的乘积
+
+nums   5    2    3    4
+res    1    1    1    1
+l      1    5   5*2 5*2*3
+r   4*3*2  4*3   4    1
+ */
+class Solution {
+    public int[] productExceptSelf(int[] nums) {
+        int l = 1, r = 1, n = nums.length;
+        int[] res = new int[n];
+        Arrays.fill(res, 1);
+        for (int i = 0; i < n; i++) {
+            res[i] *= l;
+            l *= nums[i];
+            res[n - i - 1] *= r;
+            r *= nums[n - i - 1];
+        }
+        return res;
+    }
+}
