238. 除自身以外数组的乘积_python_238. 除自身以外数组的乘积 python

【题目】

说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。

进阶：
你可以在常数空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）

【思路】

1. 审题：不能使用除法和要在O(n)时间复杂度完成，说明不能用两层for循环
2. 两个并列的for循环。
   第一个for循环：left和right两个数组储存当前值左边和右边的所有元素乘积。
   第二个for循环：将left和right相乘。

【python】

class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        #nums = [1, 2, 3, 4]
        ln =len(nums)
        left,right = [1]*ln,[1]*ln
        for i in range(1,ln):
            left[i] = left[i-1]*nums[i-1] #left = [1, 1, 2, 6]
            right[ln-i-1] = right[ln-i]*nums[ln-i] #right = [24, 12, 4, 1]
        res = [1]*ln
        for i in range(ln):
            res[i] = left[i]*right[i]
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

【结果】

【学习收获】
题目还有进阶选项：常数空间复杂度O(1)，也就是所用空间不随n的变化而变化（除了输出数组空间res）

借鉴高手代码：https://sweets.ml/2019/03/03/leetcode-238/

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n =len(nums)
        result = [1 for i in range(n)]
        result_left = 1
        result_right = 1
        for i in range(n-1):
            result_left *=nums[i]
            result[i+1] =result_left
        for i in range(n-1,0,-1): #从n-1到1
            result_right *=nums[i]
            result[i-1] *= result_right
        return result 
1
2
3
4
5
6
7
8
9
10
11
12
13