📌 Problem.

https://leetcode.com/problems/two-sum/

덧셈하여 target을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하는 문제이다.

📌 Solution.

1. 브루트 포스

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

O(N^2)의 시간 복잡도를 갖는다.

2. in을 이용한 탐색

def twoSum(self, nums: List[int], target: int) -> List[int]:
    for i, n in enumerate(nums):
        complement = target - n
        if complement in nums[i + 1:]:
            return [i, nums[i + 1:].index(complement) + i + 1]

in을 이용해 푸는 경우 역시 O(N^2)의 시간 복잡도를 갖는다.
그러나 브루트 포스와 같은 시간 복잡도를 갖더라도, 파이썬 내부 함수로 구현된 in 연산을 활용하는 것이 파이썬 레벨에서 매번 값을 비교하는 것보다 훨씬 더 가볍고 빠르다.

3. dict 자료형 활용

def twoSum(self, nums: List[int], target: int) -> List[int]:
	nums_map = {}
    for i, num in enumerate(nums):
        complement = target - num
        if (complement in nums_map) and (i != nums_map[complement]):
            return [i, nums_map[complement]]
        nums_map[num] = i

딕셔너리에 (값): (인덱스) 형식으로 데이터를 저장하고 이를 활용하여 complement를 찾아내는 방식이다.
위의 풀이는 Amortized O(N)의 시간 복잡도를 갖는다.

4. 투 포인터

def twoSum(self, nums: List[int], target: int) -> List[int]:
	left, right = 0, len(nums) - 1
    while left != right:
    		if nums[left] + nums[right] < target:
            	left += 1
            elif nums[left] + nums[right] > target:
            	right -= 1
            else:
            	return [left, right]

투 포인터로 구현하는 경우 O(N)의 시간 복잡도를 갖는다.
코드 자체도 매우 간결하고 이해하기 쉽다.

그러나 투 포인터를 활용하기 위해서는 정렬이 필수적인데, 이 문제에서는 nums를 정렬하면 인덱스가 흐트러지므로 불가능하다.
분명 다른 문제에서는 투 포인터가 좋은 방법이 될 수 있을 것이다.