[LeetCode] Two Sum (Python)

코딩에 대한 이해력을 높이기 위한 작성된 글입니다.
여기의 내용은 @NeetCode 유튜버 동영상을 기반으로 작성되었으므로, 문제 발생 시 즉각적으로 삭제하도록 하겠습니다.

LeetCode 1번 문제 (Two Sum)

문제

하지만 하단의 Follow-Up 사항을 참고 하게된다면, Time Complexity O(N^2) 해결 할 수 있는 풀이가 있는지에 대해 Challenge를 주는점 참고해야합니다.

풀이

1. Brute Force

예를 들어. nums = [2, 7, 11, 15] 라는 배열이 주어졌을때, 각각의 index를 비교하여 해결하는 Brute Force 방법이 있습니다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
    	for i in range(len(nums)):
        	for j in range(i+1, len(range(nums))):
            	if nums[i] + nums[j] == target: 
                	return [i,j] 
        

하지만 이러한 방식을 통해 해결하게 된다면, 주어진 Follow-Up에 대해 Challenge가 불가능합니다. 하나하나의 element에 대해 방문해야 하기때문에 Time Complexity 차원에서 비효율적 일 것 입니다.

2. Hash Map

Hasp Map를 사용하게 된다면, 한번의 iteration으로 결과 값을 반환할 수 있습니다.

예를 들자면,

nums = [2,1,5,3 ] 배열과 target = 4 값이 주어졌습니다.
여기서 중요한 것은 TARGET의 값과 각각 배열의 element에 차이를 구하게 된다면, 한번의 iteration을 통해 Index i와 j의 합이 target 값과 같은지 파악 할 수 있습니다.

위의 배열 같은 경우 예를 들자면, 아래의 테이블과 같이 표현할 수 있습니다.
target 값에서 element 2, 1 ,5 차이를 구하게 된다면, 중복되는 값이 없기에 비어있는 hashmap에 포함 시켜 줍니다. 하지만, 4-3 = 1 같은 경우, 이미 Hashmap에 1이라는 숫자가 포함되어 있기 때문에 포함하지 않게 됩니다.

Value	Index	Diff	Hash (key:index)
2	0	4 - 2 = 2	(2,0)
1	1	4 - 1 = 3	(1,1)
5	2	4 - 5 = -1	(5,2)



class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        prevMap = {}  # val -> index

        for i, n in enumerate(nums):
            diff = target - n
            if diff in prevMap:
                return [prevMap[diff], i]
            prevMap[n] = i