[LeetCode] 1. Two Sum

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

문제는 다음과 같다.

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.

complement 만드는 것 제외하면 별 방법이 떠오르지 않아서 그냥 brute force처럼 했는데, edge case에서 걸려서 못하고 있다가 결국 답안을 봤다... 나란 쓰레기...

정석은 다음과 같이 dictionary를 통해 hash table을 만들고, 이후에 complement의 유무와 겹침 여부를 판단해서 return을 하면된다고 한다...

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        numMap = {}
        n = len(nums)

        # Build the hash table
        for i in range(n):
            numMap[nums[i]] = i

        # Find the complement
        for i in range(n):
            complement = target - nums[i]
            if complement in numMap and numMap[complement] != i:
                return [i, numMap[complement]]

        return []  # No solution found

one-pass로 수행하는 방법도 있는데, 이 경우 간단한 코드임에도 겹치는 index를 지정하지 않을수도 있고, normal한 case를 놓치지 않아서 좋다.

[2,7,11,13]인 경우, 2는 그냥 지나가고 7부터 수행, [3,2,5]인 경우, 3은 그대로 hash table에 저장되고 방치된다. edge case를 고려하지 않아도 되는 코드.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        numMap = {}
        n = len(nums)

        for i in range(n):
            complement = target - nums[i]
            if complement in numMap:
                return [numMap[complement], i]
            numMap[nums[i]] = i

        return []  # No solution found