requirements

You are given an array of integers of length n, nums, where n > 1 returns output, where output[I] is equal to the product of all elements in nums except nums[I].

Example:

Input: [1,2,3,4] output: [24,12,8,6]Copy the code

Tip: The problem data ensures that the product of all prefixes and suffixes (or even the entire array) of any element in the array is within the range of 32-bit integers.

Note: Please do not use division and complete this problem in O(n) time complexity.

Advanced: Can you do this problem in constant space complexity? (For the sake of spatial complexity analysis, the output array is not considered extra space.)

The core code

class Solution:
    def productExceptSelf(self, nums: List[int]) - >List[int] :
        n = len(nums)
        res = [1] * n
        for i in range(1,n):
            res[i] = res[i - 1] * nums[i - 1]
        right = 1
        for i in range(n-1, -1, -1):
            res[i] *= right
            right *= nums[i]
        return res
Copy the code

Another way of thinking

class Solution:
    def productExceptSelf(self, nums: List[int]) - >List[int] :
        n = len(nums)
        res = [1] * n
        left = right = 1
        for l,r in zip(range(n),range(n-1, -1, -1)):
            res[l] *= left
            left *= nums[l]

            res[r] *= right
            right *= nums[r]
        return res
Copy the code

Key issues

Answer:

First solution: we use left and right accumulative method, take [1,2,3,4] as an example, we deliberately multiply to the previous digit, do not involve the standard, round [1,1,2,6], we experience the right side accumulative, the right side of the first cannot include themselves, use 1 substitution, [24,12,8,6], this method is very clever, worth learning. Second solution: the same left and right accumulative, pay attention to the use of ZIP.