動機
由左到右與由右到左去組合!!
Problem
Given an integer array nums
, return an array answer
such that answer[i]
is equal to the product of all the elements of nums
except nums[i]
.
The product of any prefix or suffix of nums
is guaranteed to fit in a 32-bit integer.
You must write an algorithm that runs in O(n)
time and without using the division operation.
Example 1:
Input: nums = [1,2,3,4]Output: [24,12,8,6]
Example 2:
Input: nums = [-1,1,0,-3,3]Output: [0,0,9,0,0]
Constraints:
2 <= nums.length <= 105
-30 <= nums[i] <= 30
- The product of any prefix or suffix of
nums
is guaranteed to fit in a 32-bit integer.
Follow up: Can you solve the problem in O(1)
extra space complexity? (The output array does not count as extra space for space complexity analysis.)
Sol
由左到右與由右到左,之後兩個放在一起看,再看我們的目標,就會知道怎麼走了
話說follow-up有說用常量記憶體來做,其實就是把下面的ret用成l2r就好
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
l2r = [nums[0]]
for i in range(1,len(nums)):
l2r.append(l2r[i-1]*nums[i])
for i in range(len(nums)-2,0,-1):
nums[i] = nums[i+1]*nums[i]
r2l = nums
# 1 1,2 1,2,3 1,2,3,4
# 1,2,3,4 2,3,4 3,4 4
# 2,3,4 1,3,4 1,2,4 1,2,3
ret = [r2l[1]]
for i in range(len(nums)-2):
ret.append(l2r[i]*r2l[i+2])
ret.append(l2r[-2])
return ret