[LeetCode 리트코드] two sum - python

이번에 가져온 문제는 two sum이다.
릿코드 문제 퀄리티가 좋다길래 이제부터 릿코드도 풀려고 한다.

이건 그냥 두 개의 수를 더해서 target이 되는 두 수의 인덱스를 출력하면 되는 문제다.

풀이 과정

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        length = len(nums)
    
        
        for idx1, num1 in enumerate(nums):
            for idx2 in range(idx1+1, length):
                num2 = nums[idx2]
                _sum = num1 + num2 
                
                if _sum == target:
                    return [idx1, idx2]                     

이렇게 풀어서 통과는 됐는데 O(n^2)의 시간 복잡도를 가진다.
분명 더 좋은 코드가 있을 거라서 다른 사람의 코드를 봤다.

다른 사람의 풀이 참고

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        length = len(nums)
        
        dic = {}
        for idx, num in enumerate(nums):
            if target - num in dic:
                return [idx, dic[target - num]]
            
            dic[num] = idx
        

와... 이런 방법이..
target을 만들려면 "target - 현재 수"를 가지는 수가 있으면 되니까
탐색하면서 "target - 현재 수"를 가지는 수가 있는 지 보면 되는 거였다.
이러면 O(n)으로 풀 수 있다.