Leetcode 238) Product of Array Except Self

24 May 2021 in Algorithms

• 만약 나누기를 사용할 수 있으면, 모든 원소들을 다 곱하고 하나씩 나눠주면 된다. 근데 그거는 금지됨.

• 공간도 시간도 O(n)을 사용하기 위해서, 어레이 하나에다가 다 해결한다.

  

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