[LeetCode] 238. Product of Array Except Self

本文主要是介绍[LeetCode] 238. Product of Array Except Self，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题：https://leetcode.com/problems/product-of-array-except-self/description/

题目

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.)

思路

最常用的解法是：首先 求得 nums中的所有数的乘积multi，然后对于每个res[i] =multi/nums[i] 。

本题由于限制，需要分析每个res[i]的得出过程。
1.对于每个res[i] 等于 nums中 i 左边和右边数的乘积。
2.可以通过一次遍历，得到lres[i]。lres[i] 为 nums中 位于 i 左边所有数的乘积。同理可以得到 rres[i] , 然后 res[i] = lres[i]*rres[i]。
3.由于两次遍历没有依赖关系。所以，我们可以将两次遍历 转化为 一次遍历 来完成。

code

class Solution:def productExceptSelf(self, nums):""":type nums: List[int]:rtype: List[int]"""n = len(nums) res = [1]*n left = 1right = 1i,j = 0,n-1while i<n-1:left *= nums[i]right *= nums[j]res[i+1] *= leftres[j-1] *= righti += 1j -= 1return res 

这篇关于[LeetCode] 238. Product of Array Except Self的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---