（Java）leetcode-238 Product of Array Except Self

╰+攻爆jí腚メ 2022-02-12 11:19 249阅读 0赞

# 题目 #

【数组的乘积（除了自身）】  
Given an array nums of n integers where n > 1, return an array output such that output\[i\] is equal to the product of all the elements of nums except nums\[i\].

Example:

Input:  [1,2,3,4]
    Output: [24,12,8,6]

Note: Please solve it without division and in O(n).

Follow up:  
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)

# 思路 #

关键是不能用除法，那么这个位置的乘积可以分为两部分，左半部分和右半部分。  
第一次遍历，我们在新的数组中，从左到右记录下对应位置的【左半部分】的乘积。  
第二次遍历，如法炮制，从右往左记录下对应位置的【右半部分】的乘积。  
最后把两个数组对应位置相乘，即可得到结果数组。  
时间复杂度：O(n)  
空间复杂度：O(1)

# 代码 #

class Solution { 
        public int[] productExceptSelf(int[] nums) { 
            int[] res = new int[nums.length];
            int[] left = new int[nums.length];
            int[] right = new int[nums.length];
            // 对应位置左半部分的乘积
            left[0] = 1;
            for (int i =1;i < left.length ;i++ ) { 
            	left[i] = left[i-1] * nums[i-1];
            }
            // 对应位置右半部分的乘积
            right[right.length-1] = 1;
            for(int i = right.length-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;
    
        }
    }

# 提交结果 #

![在这里插入图片描述][20191120155213744.png]

# 改进 #

上面的方法新开辟了三个数组，我们可以精简一下，只使用一个结果数组即可。  
左半部分乘积可以先保存在res中，并且在从右向左遍历的过程中只需要一个变量”right“来保存右半部分的乘积即可，在往左的过程中对这个变量进行更新。

## 代码 ##

class Solution { 
        public int[] productExceptSelf(int[] nums) { 
            int[] res = new int[nums.length];
            res[0] = 1;
            for (int i =1;i < res.length ;i++ ) { //最左端位置，最后结果中没有左半部分乘积
            	res[i] = res[i-1] * nums[i-1];//此时的res[i]记录的为该位置的左半部分的乘积
            }
            int right = 1;//右半部分的乘积，因为最右端的位置，最后结果的构成中：没有右半部分乘积，只有左半部分，所以right从1开始
            for(int i = res.length-1; i >= 0; i--){ 
            	res[i] *= right;//每个位置需要乘上对应的右半部分的乘积
            	right *= nums[i];//right进行累乘，作为下一个位置的右半部分乘积
            }
            return res;
        }
    }

## 提交结果 ##

![Runtime: 1 ms, faster than 100.00% of Java online submissions for Product of Array Except Self.Memory Usage: 43.2 MB, less than 43.31% of Java online submissions for Product of Array Except Self.][Runtime_ 1 ms_ faster than 100.00_ of Java online submissions for Product of Array Except Self.Memory Usage_ 43.2 MB_ less than 43.31_ of Java online submissions for Product of Array Except Self.]

[20191120155213744.png]: /images/20220212/e8d82556b81d43d4abb6ca5c4532a388.png
[Runtime_ 1 ms_ faster than 100.00_ of Java online submissions for Product of Array Except Self.Memory Usage_ 43.2 MB_ less than 43.31_ of Java online submissions for Product of Array Except Self.]: /images/20220212/83ce6cffca5f40f18d00d6ba1e6a1f4f.png