Two Sum

나의 논리

이런 말 하면 좀 그렇지만 가장 1번 문제고..틀릴일은 없겠다 싶어서 브루트 포스로 풀었다.
시간 복잡도는 O(n^2)인데 그나마 최적화해보겠다고 노력은 했다.
인덱스 (i,j)를 구할때 (i,j)나 (j,i)나 같으므로 안쪽 반복문은 인덱스 i 이후로 시작하게 했다.

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

정답 논리

내가 읽고 있는 파이썬 알고리즘 인터뷰라는 책에서는 브루트포스 외에도 파이써닉하게 최적화한 다른 두가지 알고리즘을 소개하고 있다.
그 중 하나 마음에 드는것을 고르자면

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

딕셔너리 자료구조를 활용해서 {숫자: 인덱스}형태로 저장한다.
그 후 반복문을 통해 숫자가 나오면 target - num이 딕셔너리의 키에 있는지 in 연산자를 통해 딕셔너리를 확인하고
있다면 인덱스를 반환한다.