[LeetCode | Python] 1. Two Sum

 

내 풀이: 브루트포스

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

        for i in range(len(nums)):
            for j in range(len(nums)):
                if nums[i] + nums[j] == target and i != j:
                    result.add(i)
                    result.add(j)

        result = list(result)

        return sorted(result)

set에다가 추가하고 리스트로 바꾸고 sorted로 리턴했다.

 

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

        return []

근데 그냥 바로 return [i, j]로 하고 없으면 빈 배열 리턴하는 게 더 깔끔한 듯!

시간 복잡도는 n^2이다.

 

Hash Map을 사용하면 O(n)에 풀 수 있다!

 

풀이 2: Two-Pass Hash Map

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

        for i, n in enumerate(nums):
            indices[n] = i

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

indices에는 값과 인덱스 저장

첫번째 패스에는 값과 인덱스를 딕셔너리에 저장,

두번째 패스에서는 target쌍을 찾음

 

풀이 3: One-Pass Hash Map

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

 

target-n으로 diff(필요한 값) 계산하고 prevMap에 있는지 확인.

-> 있으면 - 그 리스트 반환

-> 없으면 - 현재 숫자와 인덱스를 prevMap에 저장하고 다음 숫자로 넘어감