LeetCode [알고리즘] 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.

int형 배열 nums와 int형 변수 target이 주어졌을 때, 더해서 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.

순서 상관없이 반환할 수 있다.

 

나의 풀이

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)-1):
            for j in range(i+1,len(nums)):
                if nums[i] + nums[j] ==target:
                    return [i,j]

이중 반복문을 써서 배열안에 값들을 다 비교하였다.

복잡도는 n^2

 

다른 사람 풀이

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

 

딕셔너리를 사용하였다.

ax + bx = target   // ax = target - bx // ax는 유일한 bx와 쌍을 이룬다.

만약 딕셔너리에 num 값이 없으면

딕셔너리에 target - num 를 넣어준다. ( target - num를 키로, 인덱스는 값으로 딕셔너리에 추가 )

num값의 짝궁이 되는 값(target - num)을 딕셔너리에 넣어주어 이후의 num 값들 중에 딕셔너리에 존재하는 num이 있으면 리턴해준다.

복잡도는 n