[코테] 리트코드 배열 1. Two Sum 문제

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.

제한사항

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

입출력 예시 #1

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

입출력 예시 #2

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

입출력 예시 #3

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

문제 풀이

enumerate를 사용하여 값을 키로 인덱스를 값으로 하는 딕셔너리를 생성해서 풀이하면 빠르게 답을 찾을 수 있다.

## in을 이용한 탐색
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int] :
        for i, n in enumerate(nums):
            complement = target - n 

            if complement in nums[i+1:]:
                return i, nums[i+1:].index(complement) + (i+1)

## 첫 번째 수를 뺀 결과 키 조회
class Solution:
    def twoSum(self, nums: List[int], target:int) -> List[int] :
        nums_map = {}

        # 키와 값을 바꿔서 딕셔너리로 저장
        for i, num in enumerate(nums):
            nums_map[num] = i

        # 타겟에서 첫 번째 수를 뺀 결과를 키로 조회
        for i, num in enumerate(nums):
            if target - num in nums_map and i != nums_map[target-num]:
                return nums.index(num), nums_map[target-num]

## 조회 구조 개선
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums_map = {}
    
        # 하나의 for 문으로 통합
        for i, num in enumerate(nums):
            if target - num in nums_map:
                return [nums_map[target-num], i]
            nums_map[num] = i