[leetcode] [파이썬]Two Sum #001

https://leetcode.com/problems/two-sum/description/

 

 

 

 

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

 

 

이 문제를 풀기 위해 처음 접근 방법은 이중 for문을 활용했다.

그런 뒤 아래 문구처럼 시간 복잡도가 O(n2) 이하로 만족하게 작성하라는 문구를 보았다. 

Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

 

 

이 문제에서 제가 생각한 핵심 자료구조는 닥셔너리(해시)이다.

그 이유 1) 시간 복잡도가 O(1)이며 2) 임의의 숫자 키값을 이용하여 그에 응하는 값을 가져올 수 있기 때문이다.

 

 

 

해설

1. hashmap이란 딕셔너리 선언한다.

2. 파라미터 리스트 nums의 길이만큼 loop를 순환한다.

3. 각 인덱스마다 target과의 차(complement)를 구한다.

4. 만약 딕셔너리에 complement에 해당하는 값이 있는 경우, 해당 인덱스와 complement에 대한 딕셔너리 값을 배열에 담아 반환한다.

5. 그렇지 않을 경우, 딕셔너리에 각 인덱스 값(value)에 대한 인덱스(index)를 추가해준다.

6. 반복한다.