力扣 238. 除自身以外数组的乘积

题目

给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

示例

输入: [1,2,3,4]
输出: [24,12,8,6]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/product-of-array-except-self
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法1：前缀和 && 后缀和

Python实现

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n=len(nums)
        left,right=[1]*n,[1]*n
        res=[0]*n
        for i in range(1,n):
            left[i]=left[i-1]*nums[i-1]
        for i in range(n-2,-1,-1):
            right[i]=right[i+1]*nums[i+1]
        for i in range(n):
            res[i]=left[i]*right[i]
        return res
1
2
3
4
5
6
7
8
9
10
11
12

Java实现1

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        int[] prefix = new int[n];
        int[] suffix = new int[n];
        // 计算前缀积
        prefix[0] = nums[0];
        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i - 1] * nums[i];
        }
        // 计算后缀积
        suffix[0] = nums[n - 1];
        for (int i = 1; i < n; i++) {
            suffix[i] = suffix[i - 1] * nums[n - i - 1];
        }
        // 计算乘积
        for (int i = 0; i < n; i++) {
            if (i == 0) {
                res[i] = suffix[n - i - 2];
                continue;
            }
            if (i == n - 1) {
                res[i] = prefix[i - 1];
                continue;
            }
            res[i] = prefix[i - 1] * suffix[n - i - 2];
        }

        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

Java实现2

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] left = new int[n];
        int[] right = new int[n];
        int[] res = new int[n];

		//从左往右
        left[0] = 1;
        for (int i = 1; i < n; i++){
            left[i] = left[i - 1] * nums[i - 1];
        }

		//从右往左
        right[n - 1] = 1;
        for (int i = n - 2; i >= 0; i--){
            right[i] = right[i + 1] * nums[i + 1];
        }

        for (int i = 0; i < res.length; i++) res[i] = left[i] * right[i];
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23