1. Two Sum

1. brute force로 해결

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

시간 복잡도 : O(n^2)

2. in을 이용한 탐색

class Solution:
    def twoSum(self, nums, target):
        for i, n in enumerate(nums):
            complement = target - n
            
            if complement in nums[i + 1:]:
                # nums[i + 1:].index(complement)로 nums[i] 뒤에 나오는 complement의 index를 찾아주는데
                # 이 인덱스는 nums[i  + 1:]로 새로 만든 리스트에서 찾는거여서
                # nums[i + 1]의 인덱스가 0 부터 시작하기에 원래 인덱스를 구하기 위해서
                # 여기다가 i + 1만큼 더해줘야함.
                return [i, nums[i + 1:].index(complement) + (i + 1)]

시간 복잡도 : in의 시간 복잡도가 O(n)이고 전체는 O(n^2)임.

3. 첫 번째 수를 뺀 키 조회

class Solution:
    def twoSum(self, nums, target):
        dict = {}

        for i, num in enumerate(nums):
            # 키랑 값을 바꿔서 딕셔너리에 넣어줌.
            dict[num] = i

        for i, num in enumerate(nums):
            # 해당 키가 딕셔너리 안에 있는지 볼 때 in 사용하면됨
            # 자기 자신은 빼줘야함.
            if target - num in dict and i != dict[target - num]:
                return[i, dict[target - num]]

딕셔너리가 해시 테이블로 만들어졌기 때문에 조회가 O(1)에 가능함. 최악의 경우 O(n)이긴한데 이거보다는 빠를거임.

3-1. 조회 구조 개선

class Solution:
    def twoSum(self, nums, target):
        dict = {}

        for i, num in enumerate(nums):
            if target - num in dict:
            	# 안에 있는지 체크 하고 딕셔너리에 넣기 때문에 자기 자신인지 확인할 필요없음
                return [i, dict[target - num]]
            dict[num] = i

그냥 위랑 똑같은데 딕셔너리에 하나 넣을때마다 이미 구한거로 찾는거임.

문제