LeetCode - Two Sum

Description

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

 

Example 1:

Input: nums = [2,7,11,15], target = 9

Output: [0,1]

Output: Because nums[0] + nums[1] == 9, we return [0, 1].

 

Example 2:

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

Output: [1,2]

 

Example 3:

Input: nums = [3,3], target = 6

Output: [0,1]

 

Constraints:

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

 

 

Solution

제가 푼 풀이는 아래와 같습니다.

var twoSum = function(nums, target) {
    for (let i = 0; i < nums.length - 1; i++) {
        for (let j = i+1; j < nums.length; j++) {
            if (nums[i] + nums[j] === target) return [i, j];
        }
    }
};

 

 

 

 

하지만 위 풀이는 시간 복잡도가 n 제곱으로 되기 때문에 줄일 수 있는 방법을 찾아봤습니다.

크게 두 가지 방법이 있었습니다. Map과 Hash Table인데요.

둘의 공통점이 무엇일까 고민하다가 키와 값의 쌍을 가지고 있는 특징이 있다는 것을 깨달았습니다.

⭐️ 앞으로 이중 for문을 바로 사용하기보다는, 시간 복잡도를 줄이기 위해 키와 값으로 표현할 수 있는지 먼저 생각해보려고 합니다. ⭐️

 

 

 

Map 활용

섹션 1 이후로 처음 본 map 객체였습니다. map 객체에 기본적으로 존재하는 has와 get method를 활용해서 시간 복잡도를 n으로 줄여주었습니다. 왜 map을 썼을까 궁금해서 map 객체 특징을 찾아보았더니 아래와 같은 특징이 있었습니다.

• 문자열 아닌 값도 키로 사용이 가능합니다. 이 특징 때문에 Map 객체를 사용한 것 같습니다.
• 객체처럼 dot notation이나 bracket notation을 활용할 필요 없이, set, get, clear, delete 등의 이름을 가진 method를 사용할 수 있기 때문에 더 직관적으로 사용할 수 있습니다.
• 객체처럼 for문이나 Object.keys를 사용해서 키를 순회한 후 값을 얻어내는 번거로운 과정을 거칠 필요 없이, 직접적으로 .entries 메소드를 활용해서 값을 얻어낼 수 있습니다. (참고로 위와 같은 객체의 불편함 때문에 ES2017에 Object.entries가 등장하게 되었다고 합니다.)

var twoSum = function(nums, target) {
    let map = new Map();
    
    for(let i = 0; i < nums.length; i ++) {
        if(map.has(target - nums[i])) {
            return [map.get(target - nums[i]), i];
        } else {
            map.set(nums[i], i);
        }
    }
	return [];
};

 

 

Hash Table 이용

여기서 해시 테이블이란 (Key, Value)로 데이터를 저장하는 자료구조의 하나로 빠르게 데이터를 검색할 수 있는 특징이 있습니다. 앞서 봤던 Map 객체와 유사합니다. 해시 테이블이 빠른 검색 속도를 제공하는 이유는 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문입니다. 해시 테이블은 각각의 Key값에 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색하게 됩니다. 여기서 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 합니다.

이러한 특징을 활용하면 시간 복잡도를 O(n)으로 줄일 수 있습니다.

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

 

 

 

Reference

• https://mangkyu.tistory.com/102

[자료구조] 해시테이블(HashTable)이란?