1주차 - 1.Two Sum 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.

 

정수로 이루어진 nums 라는 배열과 특정 정수를 가리키는 target 을 이용하여 두 요소들의 합이 target 이 되는 요소들의 index 를 return 하세요.

 

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]

 

입문자의 답

for i in range(0,len(nums)):
    for j in range(0,len(nums)):
        if i<j and i != j:
            if target == nums[i] + nums[j]:
                return([i, j])

런타임:  4800 ms , 15.78%

메모리 사용: 14.6 MB, 10% 로 모든 면에서 상당히 저조합니다 ㅎㅎ

 

시간 복잡도: O(n^2) 로 상당히 느립니다.

 

상위 답

dic = {}
for i, num in enumerate(nums):
    if num in dic:
        return [dic[num], i]
    else:
        dic[target - num] = i

런타임:  48 ms , 90.37%

메모리 사용: 14.4 MB, 22.38%

 

시간 복잡도: O(n)

 

* 파이썬에서 dictionary 나 set 의 요소를 가져오는 것은 O(1)