【每日算法Day 4】除自身外数组的乘积：前/后缀和/积的妙用

题目链接

LeetCode 238. 除自身外数组的乘积 (opens new window)

题目描述

给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。题目数据保证数组之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。请不要使用除法，且在 O(n) 时间复杂度内完成此题。

示例

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

解题思路

记得之前做一道题目的时候为了避免额外的O(n)空间用到了前缀和，然而做这题的时候开始思想太僵只想到前缀积，没想到还有后缀积这种东西，一个元素的前缀积乘后缀积就是要求的结果。一遍从左向右遍历得到前缀积存在等长数组中，第二遍从右向左遍历得到后缀积直接乘以前缀积就能得到答案。

public int[] productExceptSelf(int[] nums) {
    int[] result=new int[nums.length];
    int k=1;
    for (int i = 0; i < nums.length; i++) {
        result[i]=k;//k临时存储当前前缀积并存在result[i]中
        k*=nums[i];
    }
    k=1;
    for (int i = nums.length - 1; i >= 0; i--) {
        result[i]*=k;//这里是已有的前缀积乘以当前后缀积k
        k*=nums[i];
    }
    return result;
}