[LeetCode] Two Sum (자바)

 

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

Two Sum - LeetCode

 

난이도 : Easy

 

배열에서 2개의 원소를 더한 값이 target과 일치하면 이 원소들의 index를 반환하는 문제입니다.

 

가장 쉬운 방법으로는 2중 for문을 이용하여 풀 수 있지만, O(N^2)의 시간복잡도를 가지게 되어 매우 느린 방법입니다.

 

어떤 숫자 num이 있을 때 target을 만들 수 있는 다른 원소는 target - num입니다. 

Map을 이용하여 <원소의 값, index>로 Map을 구성했습니다. 배열을 탐색하며 target - num가 Map에 존재하는지 확인합니다.

이 방법은 O(N)의 시간복잡도를 가집니다.

---