[LeetCode][Python] 1. Two Sums

- 문제 링크: https://leetcode.com/problems/two-sum

- 난이도: Easy

 

주어진 숫자 배열에서 합쳤을 때 target이 되는 원소 두 개를 찾아 인덱스를 반환하는 문제다

완전탐색은 O(n^2)의 시간복잡도를 갖는다

해시테이블을 만들어서, 각 원소 x마다 target-x가 해시테이블에 존재하는지 체크하면 된다

 

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        h = {}
        for i, x in enumerate(nums):
            h[x] = i
        for i, x in enumerate(nums):
            if target - x in h:
                j = h[target-x]
                if i == j:
                    continue
                return [i, j]