[LeetCode] Two Sum

 

 

문제

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

 

 

 

설명

 

문제는 굉장히 쉽습니다. nums 리스트 안의 값 중 target값을 만족하는 두 값을 찾고 그 두값의 index를 return 하면 됩니다!

 

 

1. 가장 먼저 떠오르는 방법은 2중 for문을 활용해 인덱스의 조회를 통한 탐색방법이 있습니다.

 

근데, 1번의 방법은 O(n^2)의 시간복잡도가 필요하죠,, 시간이 너무 오래 걸린다는 말입니다.

 

따라서 다른 더 빠른 방법을 생각해봐야 합니다.

// 1번 방법
for (int i=0;i<nums.size()-1;i++) {
	for (int j=i+1;j<nums.size();j++) {
    
    }
}

 

 

 

2. HashMap을 활용한 값의 짝 찾기

 

무슨말이냐면, Example 1을 예시로 nums의 첫 값부터 체크를 해줍니다.

 

첫 값인 2가 정답이 되려면, target - 2의 값 인덱스를 역시 알고 있어야 합니다.

 

이는 곧 HashMap에 2와 함께 그 index를 저장해두고

이후에 target - 2값이 나온다면 HashMap에 저장되어 있는 2의 index값, target - 2의 index 값을 return 해주면 되는 것입니다.

 

코드로 확인해본다면,,

unordered_map<int, int> map;
for (int i=0;i<nums.size();i++) {
	if (map.find(target - nums[i]) != map.end()) {
    	return { i, map[target - nums[i]] };
    } else {
    	map.insert(make_pair(nums[i], i));
    }

}

 

위 처럼 map의 key값은 nums안의 값으로, value값은 index 값으로 설정해 1번의 탐색으로 target을 만족하는 값을 찾을 수 있게 된다!

 

시간 복잡도는 O(n)으로 감소!!

하지만 공간 복잡도는 map을 사용함으로, O(n)으로 증가!

 

 

끘!