[LeetCode] Two Sum

문제

풀이

Brute Force 방식과는 달리 HashMap를 사용하게 된다면, 한번의 Iteration으로 결과 값 도출이 가능합니다.

nums = [2,1,5,3] 배열과 target = 4 값이 주어졌다고 가정해보겠습니다. 

Value	Index	Difference	Hashmap
2	0	4 - 2 = 2	(2,0)
1	1	4 - 1 = 3	(1,1)
5	2	4 - 5 = -1	(5,2)

처음으로 Target 값에서 각 배열의 element 차이를 구합니다. 이를 통해 도출되는 Difference 값이 중복되지 않았다면 Hashmap에 포함시켜주고, 중복 되어있다면 포함시키지 않습니다. 

Class Solution: 
	def twoSum(self, nums: List[int], target: int) -> List[int]:
        prevMap = {} 
        for i,n in enumerate(nums):
        	diff = target - n
            if diff in prevMap:
            	return[prevMap[diff],i]
            prevMap[n] = i