[LeetCode] 1. Two Sum

기본 아이디어

• 이중포문하면 되겠지만 느릴듯

이중포문 - O(n²)

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)-1):
            for j in range(i+1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]

해시 - O(n)

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_map = {}
        for i, num in enumerate(nums):
            diff = target - num
            if diff in num_map:
                return [num_map[diff], i]
            num_map[num] = i

• target - num이라는 diff값이 이미 num_map에 존재한다면, 이건 target으로 만들기가 가능한 조합이라는 뜻!
• 그러므로 바로 반환
• 메모이제이션 처럼 값 저장해놓는 것

---

• 리트코드 첨 써봐!