개요

LeetCode #1, Two Sum 문제를 풀어봅니다.

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.

Example 1:

Input: nums = [2,7,11,15], target = 9 Output: [0,1] Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6 Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6 Output: [0,1]

Constraints:

• 2 <= nums.length <= 103
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.

twoSum 함수는 일일이 하나씩 for문으로 체크해서 하는 brute force 방식입니다. 효율적이지 않습니다. twoSum_ver2 함수는 nums에 enumerate을 이용해서 index와 value를 뽑아내 딕셔너리에 value를 key로, index를 value로 넣고, 그 딕셔너리에 target - num이 key로 존재하면 바로 조회해서 index를 뽑도록 합니다. Brute Force보다 빠릅니다.

class Solution:
    
    # Brute Force
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i,j]
    
    def twoSum_ver2(self, nums: List[int], target: int) -> List[int]:
        
        nums_map = {}
        for i, num in enumerate(nums):
            if target - num in nums_map:
                return [nums_map[target - num], i]
            # switch key, value to return index 
            nums_map[num] = i