238. Product of Array Except Self

Description

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.

-> 정수 배열 nums가 주어 집니다. 배열 answer의 answer[i]는 nums[i]를 제외한 모든 nums 요소의 곱과 같도록 배열 응답을 반환합니다.

nums[i]의 앞(nums[0] * nums[1] * ... nums[i-1] 또는 뒤(nums[i+1] nums[i+2] ... nums[nums.length-1])에 있는 모든 곱은 32비트 정수에 맞도록 보장됩니다.

나눗셈을 사용하지 않고 O(n) 시간에 실행되는 알고리즘을 작성해야 합니다.

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
• nums[i]의 앞(nums[0] * nums[1] * ... nums[i-1] 또는 뒤(nums[i+1] nums[i+2] ... nums[nums.length-1])에 있는 모든 곱은 32비트 정수에 맞도록 보장됩니다.

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.)
-> Follow up: O(1)의 공간 복잡도에서 문제를 해결할 수 있습니까? (출력 배열은 공간 복잡도 분석을 위한 여분의 공간으로 계산되지 않습니다.)

Solution

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] prefix = new int[nums.length];
        prefix[0] = 1;
        for (int i = 1; i < nums.length; i++) {
            prefix[i] = prefix[i - 1] * nums[i - 1];
        }

        int[] sufix = new int[nums.length];
        sufix[nums.length - 1] = 1;
        for (int i = nums.length - 2; i >= 0; i--) {
            sufix[i] = sufix[i + 1] * nums[i + 1];
        }

        int[] answer = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            answer[i] = prefix[i] * sufix[i];
        }

        return answer;
    }
}