[LeetCode] 1. Two Sum (Python)

Problem

 

Solution

hash

hash를 사용해서 푸는 문제. 문제에서도 O(n^2) 보다 더 적은 시간 복잡도로 푸는것을 권장했다.

아래는 1등 풀이

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

 

일반 for 문을 사용할 경우:

일단 숫자 num를 첫번째 nums의 인덱스 값으로 지정하고, target - num 를 찾아가는 방식이다. 인덱스는 i~len(nums) 까지 순회한다.

enumerate 을 사용하여 for 문을 사용할 경우:

i, num으로 순회하면서 target-num 값을 찾아가는 방식.

 

만약 dictionary에 존재하지 않으면 하나씩 dict에 저장해간다.

그러다가 원하는 값 (target-a)가 dict에 존재하면 바로 리스트 반환

• nums를 한 번 순회하면서 해시맵을 활용하여 연산을 처리하므로, 시간복잡도는 O(n)
• 공간복잡도는 O(n) (해시맵에 최대 n개의 값이 저장될 수 있다).

 

Code

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

 

Complexity

Time Complexity

이중포문을 사용했으므로 O(n^2)

 

Space Complexity

answer 외에 추가적인 변수는 사용하지 않았으므로 O(1)