146 - 238 除自身外数组的乘积

题目

给定长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

示例:

输入: [1,2,3,4] 输出: [24,12,8,6]

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

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

解答

第一反应，就是暴力相乘。。

两次遍历

一个非常巧妙的做法。

前后遍历两次，前往后遍历，乘一下除了该位，左边的乘积。也就是累乘在一个数里面。

后往前遍历也是一样，乘一下右边的乘积。

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

Runtime: 120 ms, faster than 98.57% of Python3 online submissions for Product of Array Except Self.

Memory Usage: 19.4 MB, less than 96.00% of Python3 online submissions for Product of Array Except Self.

var productExceptSelf = function(nums) {
  product = 1
  ans = new Array(nums.length)
  for (let i = 0; i < nums.length; i++) {
    ans[i] = product
    product *= nums[i]
  }
  product = 1
  for (let i = nums.length - 1; i >= 0; i--) {
    ans[i] *= product
    product *= nums[i]
  }
  return ans
};

Runtime: 96 ms, faster than 27.36% of JavaScript online submissions for Product of Array Except Self.

Memory Usage: 42.7 MB, less than 16.00% of JavaScript online submissions for Product of Array Except Self.

func productExceptSelf(nums []int) []int {
    ans := make([]int, len(nums))
    product := 1
    for i, v := range nums {
        ans[i] = product
        product *= v
    }
    product = 1
    for i := len(nums) - 1; i >= 0; i-- {
        ans[i] *= product
        product *= nums[i]
    }
    return ans
}

Runtime: 1544 ms, faster than 25.89% of Go online submissions for Product of Array Except Self.

Memory Usage: 9.1 MB, less than 100.00% of Go online submissions for Product of Array Except Self.