LeetCode No.238 - Product of Array Except Self

카테고리: Algorithms

January 19, 2022

문제링크

접근

배열의 모든 원소들의 곱을 미리 구한다음 나눗셈을 이용하여 정답을 구하는 방법이외에 O(n)의 시간으로 정답을 구하는 방법은 다음과 같이 각 원소의 왼쪽, 오른쪽 곱을 각각 구하여 이들을 구하는 방법이 있을 수 있습니다:

왼쪽/오른쪽 곱
왼쪽/오른쪽 곱

자바스크립트 풀이

function productExceptSelf(nums) {
  const { length } = nums;
  const answer = Array.from({ length }, () => 1);
  
  // calculate left product of each element
  let acc = 1;
  for (let i = 0; i < length; i++) {
    answer[i] *= acc;
    acc *= nums[i];
  }
  
  // accumulate right product of each element
  // to the left product we previously calculated
  acc = 1;
  for (let i = length - 1; i >= 0; i--) {
    answer[i] *= acc;
    acc *= nums[i];
  }
  
  return answer;
}