[Leet code] 1. Two Sum

Category	ps/브루트 포스
Tag	브루트 포스
Tags	dict
난이도	★
발행 여부
사이트	Leet code
실수 유형
이해	완벽히 이해
최종 편집 일시	@2021년 11월 14일 오후 5:43
푼 날짜	@2021년 11월 14일 오후 5:28

문제 해설 및 주의사항

원문

번역 및 주의사항

풀이

내 풀이 코드

풀이 코드 (complement)

풀이 코드 (dictionary)

퇴고

문제 해설 및 주의사항

원문

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]

번역 및 주의사항

정수 배열 nums 와 정수 target 이 주어진다.

nums 의 두 수를 더해서 target 이 되는 index 를 반환해라

Constraints:

• 2 <= nums.length <= 104

• 109 <= nums[i] <= 109

• 109 <= target <= 109

• Only one valid answer exists.

---

풀이

내 풀이 코드

2중 for 문 brute force

풀이 코드 (complement)

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]

풀이 코드 (dictionary)

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

---

퇴고

• 간단한 문제더라도 풀이는 다양하며 그에 따른 실행 속도는 천차만별이다. 시간복잡도를 고려하고 효율성 있는 풀이를 생각해야한다.

• 파이썬의 느린 속도를 감안하여 C++ 로 풀던 것보다 정밀히 코드를 구현해야한다.