LeetCode알고리즘 Two Sum문제

오늘은 LeetCode 알고리즘 문제를 풀어보겠습니다.

처음부터 차근차근 :)

 

문제 제목은 Two Sum이며 설명은 아래와 같습니다.

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.

정수 배열이 주어지며, 두 수를 더해 타겟이 되는 수의 인덱스를 리턴해라.

각 입력에는 하나의 답만 존재하며, 동일한 원소가 두 번 나오지 않는다고 가정한다.

 

음 예시를 보면 확실히 알 것 같습니다.

 

예를 들어 [2,7,11,15] 정수 배열과 목푯값 9가 주어집니다.

정수 배열중 두 수를 더해 목푯값을 만족하는 수의 인덱스를 리턴해줍니다.

위에서는 2와 7을 더하면 목푯값인 9가 되겠네요. ( 2 + 7 = 9 )

그럼 2와 7의 인덱스 [0,1]을 리턴해주면 됩니다.

 

이제 문제를 풀어봅니다.

저는 가장 먼저 생각해낸 방법이 그냥 다 확인해주는 방법입니다.

버블 정렬과 같이 for 루프를 두 번 돌면서 하나씩 다 맞춰보는 방식입니다.

시간 복잡도는 O(n^2)이며 공간 복잡도는 O(1)입니다.

 

여기서 시간 복잡도를 개선해보겠습니다.

시간 복잡도를 개선해 O(n^2)보다 작은 시간 복잡도를 만들어야 합니다.

 

또 다른 방법은 해시 테이블을 사용하는 것입니다.

for 루프를 한 번만 돌면서 target - nums[i]의 값이 해시 테이블의 키로 존재하는지를 확인합니다.

존재한다면 return 해주는 방법입니다.

 

아까 문제 풀이는 a + b = c 느낌으로 접근했다면 이 방법은 b = c - a 느낌으로 접근해보겠습니다.

(여기서 a와 b는 주어진 정수 배열의 각각의 값이고 c는 target이라 생각하면 될 것 같습니다.)

 

해시 테이블을 사용해 시간 복잡도를 O(n)으로 줄일 수 있었습니다.

하지만 해시 테이블을 사용했기 때문에 공간 복잡도는 O(n)입니다.

 

https://leetcode.com/problems/two-sum/