LeetCode - 525. Contiguous Array (JavaScript)

Medium, Hash

RunTime : 14 ms / Memory : 57.42 MB

문제

Given a binary array nums, return the maximum length of a contiguous subarray with an equal number of 0 and 1.

풀이

1. 처음엔 누적합 psum으로 접근했다.

• 답은 맞았지만, 시간적으로 느려서 새로운 접근법이 필요했다.
• 시간복잡도는 O(n)

var findMaxLength = function (nums) {
  const n = nums.length;
  let psum = Array(n + 1).fill([0, 0]);
  psum[0] = [0, 0];
  // count 0, count 1

  for (let i = 1; i < n + 1; i++) {
    if (nums[i - 1] === 0) {
      psum[i] = [psum[i - 1][0] + 1, psum[i - 1][1]];
    } else {
      psum[i] = [psum[i - 1][0], psum[i - 1][1] + 1];
    }
  }

  let idxMap = new Map();
  idxMap.set(0, 0);
  let res = 0;
  for (let idx = 1; idx < n + 1; idx++) {
    const diff = psum[idx][0] - psum[idx][1];

    if (idxMap.has(diff)) {
      res = Math.max(res, idx - idxMap.get(diff));
    } else {
      idxMap.set(diff, idx);
    }
  }

  return res;
};

2. GPT랑 다른 사람의 풀이를 보니 단순하게 HashMap을 통해 해결했다.

• 1이 등장할때 cnt를 +1해서 둘의 차가 같은 인덱스 간의 비교를 하는 방식
• 시간복잡도는 O(n)

var findMaxLength = function (nums) {
  const n = nums.length;
  let res = 0;

  let cntMap = new Map();
  cntMap.set(0, -1);

  let cnt = 0;
  for (let i = 0; i < n; i++) {
    cnt += nums[i] === 1 ? 1 : -1;

    if (cntMap.has(cnt)) {
      res = Math.max(res, i - cntMap.get(cnt));
    } else {
      cntMap.set(cnt, i);
    }
  }

  return res;
};