[LeetCode] 1. Two Sum (C++)

문제

숫자 배열에서 두개의 합이 x가 된다. 이때 두개의 수를 찾아라.

처음 풀이

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> res; 
        for(int i=0; i<nums.size()-1; i++){
            for(int j=i+1; j<nums.size(); j++){
                if(nums[i] + nums[j] == target) {
                    res.push_back(i);
                    res.push_back(j);
                }
            }
        }
        return res;
    }
};

개선할 점

나는 브루트 포스 방식으로 풀었다. 이는 O(n^2)의 시간 복잡도를 갖는다.

이 문제는 O(n)의 시간복잡도로 개선할 수 있다.

unordered_map을 사용해야 한다!

💡 unordered_map

• 해시테이블로 구현한 자료구조로 map보다 더 빠른 탐색을 하기 위한 자료구조
• 특징
  • 중복된 데이터를 허용하지 않음
  • 정렬되지 않으며 해시 함수를 사용하여 원소를 탐색
• 탐색 시간복잡도 O(1)
  • hashmap은 해시 함수로 탐색을 하므로 평균 O(1)
  • 해시 충돌이 많이 일어나는 최악의 경우 O(N)
• 사용 방법
  • #include <unordered_map> 헤더를 선언해야 한다.

💡 map

• 바이너리 서치 트리로 구현한 자료구조
• 특징
  • 중복된 데이터를 허용하지 않음
  • 자동으로 원소들이 순서대로 정렬되어 들어감
    • default는 key값을 기준으로 오름차순 정렬
• 탐색 시간복잡도 O(logN)
  • 정렬되어있는 상태에서 탐색을 하므로 평균, 최악 모두 O(logN)

결과

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> m;
        for(int i=0; i<nums.size(); i++){
            // 각 요소에 대해 타겟에서 현재 요소를 뺀 값이 해시 테이블에 있는지 확인
            if(m.find(target - nums[i])!=m.end()){
                // 있으면 해당 키에 저장된 인덱스와 현재 인덱스를 리턴
                return {m[target - nums[i]], i};
            }

            // 없으면 현재 값을 키로 인덱스를 저장
            m[nums[i]] = i;
        }
        return {};
    }
};