Grind75 - 1. Two Sum 파이썬

1. Two Sum

 

Easy

---

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]
Explanation: 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 <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.

 

Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

 

 

힌트:

브루트 포스(모든 경우의 수 확인) 하면 O(N^2) 나온다. 그러면 시간초과

해시맵(딕셔너리)를 만들고 키값을 nums를 돌며 만드면서 동시에 dic.keys()안에 정답값 - 현재값이 있는지 확인한다.

그러면 O(N)이 나온다.

 

프로그래머스 풀다가 뭔가 알고리즘에 대한 느낌이 살짝살짝 오는듯해서 빠르게 외국의 유명한 Grind75라는 리트코드에서 한 유저가 만든 유명문제 모음집으로 갈아탔다 여기서 시간복잡도와 문제유형별 어떤 자료구조와 알고리즘을 써야하는지 알아보도록 해야겠다.

 

일단 시험부터 잘 치자...

 

나의 코드

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dic = {nums[0]: target - nums[0]}
        for i in range(1, len(nums)):
            dic[nums[i]] = target - nums[i]
            if target - nums[i] in dic.keys():
                one = nums.index(target - nums[i])
                if one == i:
                    continue
                return [one, i]