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