[Python] Leet Code 1. Two Sum

본 내용은 <파이썬 알고리즘 인터뷰>를 참고했습니다.

풀이 1. 브루트 포스(가장 느림)

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:

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

풀이 2. in을 이용한 탐색

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:

        for i, a in enumerate(nums):
            b = target - a

            if b in nums[i+1:]:
                return[nums.index(a), nums[i+1:].index(b) + (i+1)]

이 문제에서 알아야할 포인트

• 인덱스 찾기
  • list에서 값을 이용해 인덱스를 찾을 때 - nums.index(a)

풀이 3. 첫번째 수를 뺀 결과 키 조회

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:

        nums_dict = {}
        for i, v in enumerate(nums):
            nums_dict[v] = i

        for i, v in enumerate(nums):
            comp = target - v
            if (comp in nums_dict) and (i != nums_dict[comp]):
                return [i, nums_dict[comp]]

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:

        nums_dict = {}
        for i, v in enumerate(nums):
            comp = target - v
            if (comp in nums_dict) and (i != nums_dict[comp]):
                return [i, nums_dict[comp]]
            nums_dict[v] = i

이 문제에서 알아야할 포인트

• list의 value를 dict의 key로, index를 value로 저장
• 해당하는 value가 dict에 있는지는 간단하게 key in dict로 조회 가능
• 중복 제외