[알고리즘] 2 Sum 찾기 - Hash Table 이용한 알고리즘 문제

leetcode.com/problems/two-sum/

Two Sum - LeetCode

리트 코드 알고리즘, 1번 문제.

쉬운 문제이고 다양한 방법으로 풀 수 있지만 Hash Table의 원리를 이용하면 시간복잡도가 더 최적화된 방법으로 풀 수 있다.

 

Approach

Hash Table이 적용된 HashMap 을 이용한다. 

HashMap의 search (get이나 containsKey method) 는 key 기준이므로 value를 key에 두어야한다. 

 

map.put(nums[index], index)

위 소스 로 HashMap key에 실제 숫자가 들어가게 HashMap을 체워나간다.

 

HashMap 안에 값이 들어가 있다면 sum이 되는 경우를 찾기 시작할 수 있다.

nums 안에 있는 숫자 a와 b가 더했을 때 target 이 되는 경우를 찾는것인데, 

b 는 이미 HashMap 안에 있다고 가정하고 a + b = target 식을 이용하여 b 를 찾는다.

 

map.containsKey(target - nums[index])

 

b = target - a  가 성립하므로 위의 소스는 HashMap에 b가 있는지 없는지를 찾는 소스가 된다.

a 위치에는 loop를 돌려 nums의 값을 순서대로 넣어준다.

b가 key로 존재하면 a와 b를 알아낸 것이므로 return 해준다.

(문제가 너무 친절하게 exactly one solution이라고 나와있기 때문에)

 

loop를 2개를 돌려서 미리 HashMap을 체우고 검색하는 loop는 따로 두어도 되지만

loop 하나로 아래처럼 검색하면서 동시에 체워넣는것도 가능하다.