[LeetCode] 238. Product of Array Except Self

Medium
Related Topics: Array / Prefix Sum
LeetCode Source

解题想法

这题我是看别人解法

原本以为要用 bit multiplication

Python

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

C++

class Solution {public:    vector<int> productExceptSelf(vector<int>& nums) {        vector<int> res(nums.size(), 0), left(nums.size(), 0), right(nums.size(), 0);        left[0] = 1, right[nums.size()-1] = 1;        for (int i = 1; i < nums.size(); i++) {            left[i] = left[i-1] * nums[i-1];        }        for (int i = nums.size() - 2; i >= 0; i--) {            right[i] = right[i+1] * nums[i+1];        }        for (int i = 0; i < nums.size(); i++) {            res[i] = left[i] * right[i];        }        return res;    }};

这系列文被记录在 Top Interview 150 Series