1. Two Sum (Array, Hash Table)

링크 - https://leetcode.com/problems/two-sum/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Easy

Intuition

이 문제는 hash table을 사용하여 two-pass방법과 one-pass방법을 사용하여 풀 수 있다.

two-pass는 먼저 hash table에 num과 index를 다 저장하고, 다시 for문을 돌면서 target-num을 찾아 반환하는 방법이다.

one-pass는 첫 for문에서 target-num이 있는지 확인하고, 없으면 hashmap에 num과 index를 저장하는 방법이다.

Code

# Two Pass
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hash_table = {}
        for i in range(len(nums)):
            hash_table[nums[i]] = i
        for i in range(len(nums)):
            complement = target - nums[i]
            if complement in hash_table and hash_table[complement] != i:
                return [i, hash_table[complement]]
        # If no valid pair is found, return an empty list
        return []

# One Pass
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hash_table = {}
        for i, num in enumerate(nums):
            if target - num in hash_table:
                return [hash_table[target - num], i]
            else:
                hash_table[num] = i
        return []

Complexity

Time Complexity: O(n) linear하기 때문이다.

Space Complexity: O(n) hash table에 저장되는 개수는 최대 n개이다.