1.md

1. Two Sum

solution 1

시간복잡도 : O(N^2)

알고리즘 : 완전 탐색

풀이 설명 : 가능한 모든 쌍에 대해서 합을 구하고 target과 같으면 return합니다.

소스코드 : link

solution 2

시간복잡도 : O(N)

알고리즘 : 해시 테이블

풀이 설명 : nums에 있는 값을 순차적으로 방문하며 target - nums[i]가 이전에 방문한 값 중에 있다면 return합니다. 이전에 방문한 값인지 확인하기 위해 python의 dictionary를 사용하며 O(1)만에 확인할 수 있습니다.

소스코드 :

class Solution(object):
    def twoSum(self, nums, target):
        dic = {}
        for i in range(len(nums)):
            x = nums[i]
            y = target - x
            if y in dic:
                j = dic[y]
                return [j, i]
            else:
                dic[x] = i