[leetcode] twoSum

문제 :https://leetcode.com/problems/two-sum/

해결방법

const twoSum = (nums, target) => {
  const arr =[];
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        arr.push(i);
        arr.push(j);
      }
    }
  }
  return arr
}

수정

const twoSum = (nums, target) => {
  const arr = [];
  nums.forEach((num,i) => {
    nums.forEach((num, j) => {
      if (j > i && nums[i] + nums[j] === target)
        arr.push(i, j);
    })
  })
  return arr;
}

기존의 for문 대신 forEach를 사용하는 방법으로 수정해보았다.
어디선가 for문은 촌스럽다!하는 글을 보고 시도해보았지만 runtime은 3배쯤 증가하고 memory도 0.5MB쯤 더 사용하는 것을 보고 그냥 촌스럽게 써야겠다는 생각을 했다.

참고로 if 안에 j > i를 넣은 건 해당 조건을 넣지 않을 경우 중복되는 경우의 수가 나오기 때문이다.

for문을 통해 배열을 2개 놓고 하나씩 짝지어가며 비교하는 거라 O(n^2)만큼의 시간이 걸린다.

다른 풀이를 보니 hash table을 사용한 방법도 있었다. 당연하지만 나는 생각 못 했다ㅋㅋ....

해당 블로그에서 hash table을 사용한 방법을 more elegant solution이라고 말하는데 나도 곧 그런 elegant solution을 먼저 생각하는 날이 올거라 믿는다.

hash table 사용

const twoSum = (nums, target) => {
  const hash = {};
  for (let i = 0; i < nums.length; i++) {
    const otherNum = target - nums[i];
    if (hash[otherNum] !== undefined) {
      return [hash[otherNum], i];
    }
    hash[nums[i]] = i;
  }
}

for문을 한 번 쓰다보니 O(n)만큼의 시간이 걸린다.
어떤 때에 hash table을 써야하는지 다시 한 번 기억할 기회였다.