除自身以外数组的乘积 题解

题目详情

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

示例 1:

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

示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

提示：

  • 2 <= nums.length <= 105
  • -30 <= nums[i] <= 30
  • 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内

进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）

解题思路与题解

此题题目已经很明确了，解题思路，我主要推荐空间换时间

题解一

当然，老套路，这种题的暴力解法

1
2
3
4
5
6
7
8
9
10
11
12
public static int[] productExceptSelf(int[] nums) {
    List<Integer> collect = new ArrayList<>(Arrays.stream(nums).boxed().toList());
    int[] self = new int[nums.length];
    for (int i = 0; i < nums.length; i++) {
        Integer integer = collect.get(i);
        collect.set(i, 1);
        int reduce = collect.stream().mapToInt(x -> x).reduce(1, Math::multiplyExact);
        self[i] = reduce;
        collect.set(i, integer);
    }
    return self;
}

当然超时也是在意料之中的

image-20231214204020073

题解二

在描述解法二的时候，我们来回忆一下，什么是前缀积，什么是后缀积

简单来说：前缀和就是从左到右，依次将前面的数相乘 后缀和就是从右到左，依次将后面的数相乘

在本题就是一个经典的前缀积和后缀积糅杂在一起的题目

下面是一个解题步骤

nums[] = [1,2,3,4] 执行一次前缀积之后变成 => [1,2,6,24]

因为本题要求不包含本身，所以

nums[] = [1,2,3,4] 执行一次前缀积之后变成 => [1,1,2,6]

所以，在执行一次前缀积之后必然有一个数，执行了全部的乘积，如果此时我们再执行一次后缀积，那么就能达到题目所想要的结果了

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
public static int[] productExceptSelfB(int[] nums) {
    int len = nums.length;
    if (len == 0) return new int[0];
    int[] ans = new int[len];
    ans[0] = 1;
    int tmp = 1;
    // ans[] = [1,0,0,0] nums[] = [1,2,3,4]
    for (int i = 1; i < len; i++) {
        // 第一次 ans[1] = ans[0] *nums[0] = 1 * 1 = 1
        // 第二次 ans[2] = ans[1] *nums[1] = 1 * 2 = 2
        // 第三次 ans[3] = ans[2] *nums[2] = 2 * 3 = 6
        ans[i] = ans[i - 1] * nums[i - 1];
    }
    // 此时 nums[] = [1,2,3,4] ans[] = [1,1,2,6]
    //  此时 int i = 2
    for (int i = len - 2; i >= 0; i--) {
        // 第一次 tmp = 1 * nums[3] = 1 * 4 = 4 ans[2] = ans[2] * tmp = 2 * 4 = 8
        // 第二次 tmp = 4 * nums[2] = 4 * 3 = 12 ans[1] = ans[1] * tmp = 1 * 12 = 12
        // 第三次 tmp = 12 * nums[1] = 12 * 2 = 24 ans[0] = ans[0] * tmp = 1 * 24 = 24
        tmp *= nums[i + 1];
        ans[i] *= tmp;
    }
    // 此时 nums[] = [1,2,3,4] ans[] = [24,12,8,6]
    return ans;
}

image-20231214212126342

题解三

有兴趣的同学可以尝试理解下，本质就是维护两个指针，beforeSum表示前缀和，afterSum表示后缀和，在一个for循环中进行解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static int[] productExceptSelf(int[] nums) {
    int n=nums.length;
    int[] ans=new int[n];
    Arrays.fill(ans,1);
    int beforeSum=1;
    int afterSum=1;
    for(int i=0,j=n-1;i<n;i++,j--){
        ans[i] = ans[i] * beforeSum;
        ans[j] = ans[j] * afterSum;
        beforeSum = beforeSum * nums[i];
        afterSum = afterSum * nums[j];
    }
    return ans;
}