[leetcode]525. Contiguous Array

문제

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

예시

• Example 1:

  	- Input: nums = [0,1]
  	- Output: 2
  	- Explanation: [0, 1] is the longest contiguous subarray with an equal number of 0 and 1.

• Example 2:

  	- Input: nums = [0,1,0]
  	- Output: 2
  	- Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.

제한사항

1 <= nums.length <= 105
nums[i] is either 0 or 1.

풀이

const findMaxLength = (nums) => {
  const hash = {};
  let max_length = 0;
  let count = 0;
  for (let i = 0; i < nums.length; i++) {
      console.log(max_length, hash)
    const current = nums[i];
    if (current === 0) {
        // if the current element is 0, then we decrement the count
      count--;
    } else if (current === 1) {
        // if the current element is 1, then we increment the count
      count++;
    }

    if (count === 0) {
        // if the count is equal to o then we have a contiguous subarray of length equal to i+1
      max_length = i + 1;
    }
      
      //hash를 통해 0이 되려면 어디까지를 버려야 하나를 계산
    if (count in hash) {
    
      max_length = Math.max(max_length, i - hash[count]); // update our max length
    } else {
      hash[count] = i;
    }

  }
  return max_length;
};

for문을 1회만 써야하기 때문에 count = 0 에서 값이 0이면 -1, 1이면 +1을 하는데, count의 값들을 hash에다가 저장하여, count와 동일한 array가 있었다면, 그 array를 빼주면 count의 값을 0으로 만들 수 있다.

그외

시간복잡도를 줄일 수 있는 이런 개념들을 기억해야겠고, hash, slidingWindow와 비슷한 개념들이 많이 있는 것 같다.