[LeetCode][Array] Two Sum

1. 문제

  매우 유명한 (알고리즘 풀이 입문 시 자주 맞닥뜨리는) 문제이다.

정수들이 담긴 배열 nums와 목표 target이 주어질 때, 배열 nums 내의 특정 두 수의 합은 target이 된다.

해당 두 수의 index를 return해라.

 

2. 풀이

  2가지 풀이 방법으로 풀어보자.

 

  1) Two Pointer : 두개의 포인터를 가지고 배열을 탐색하는 기법이다.         a. 배열을 오름차순으로 정렬한다. 이 때, 기존 idx를 보존할 수 있도록 [num, idx] 형태로 저장 후 정렬한다.     b. 두개의 포인터(left = 0, right = len(nums)-1)를 만들고 합(nums[left][0] + nums[left][1])을 구한다.     c. (반복) 합이 target보다 작은 경우 left를 오른쪽으로 한칸, 클 경우에는 right를 왼쪽으로 한칸 이동시킨다.     d. 합이 target과 일치하면, 두 수의 idx를 반환한다.

 

  시간 복잡도 : O(nlogn)

  공간 복잡도 : O(1)

 

  2) Hash Map :  배열을 순차적으로 탐색하며 확인한 내용을 해시 맵에 기록한다. Two Pointer 보다 속도가 빠르지만, 메모리를 추가적으로 사용한다.

 

    a. nums를 순차적으로 탐색하며 아래의 과정을 수행한다.      탐색 과정의 정수 : num      a-1) Hash Map의 key들 중 num이 있는지 확인한다.      a-2) 있다면 해당 key의 value와 num의 idx를 return하고, 없다면 Hash Map에 key : target - num. value : idx 로 기록한다.          시간 복잡도 : O(n)    공간 복잡도 : O(n)