[Hash Table] Two Sum

1. Two Sum

지문은 링크에서 확인해주세요.

1. 해답을 보지 않고 스스로 문제를 해결한 과정

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 
 * Runtime	: 56 ms
 * Memory	: 42.15 MB
 */
var twoSum = function(nums, target) {
  const hash = {};

  for(let i = 0; i < nums.length; i++) {    
    const key = target - nums[i];    

    if(nums[i] in hash) {      
      return [hash[nums[i]], i];
    }

    hash[key] = i;
  }
};

Example 2를 예로

Input: nums = [3,2,4], target = 6
Output: [1,2]

루프 마다 해시 테이블의 상태는 다음과 같습니다.

1번째 루프:	{}
2번째 루프:	{ '3': 0 }
3번째 루프:	{ '3': 0, '4': 1 }

2. 여러 해답을 직접 찾아서 자신이 작성한 알고리즘에 대해서 회고한 내용

2-1. Using two pointers

해답의 전문은 링크를 확인해주세요.

/*
 * Runtime	: 117 ms
 * Memory	: 42.15 MB
 */
var twoSum = function (nums, target) {
  let left = 0;
  let right = 1;

  while (left < nums.length) {
    if (nums[left] + nums[right] === target) {
      return [left, right];
    } else if (right === nums.length -1) {
      left++;
      right = left + 1;
    } else {
      right++;
    }
  }
};

필자의 해답과 달리 공간복잡도를 줄일 수 있는 해답입니다.