LeetCode - 1. Two Sum

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int size = nums.size();
        vector<int> answer;
        for (int i=0; i<size; i++) {
            int left = target - nums.at(i);
            auto b = find(nums.begin()+i+1, nums.end(), left);
            if (b != nums.end()) {
                answer.push_back(i);
                answer.push_back(distance(nums.begin(), b));
                break;
            }

        }
        return answer;
    }
};

처음에는 단순하게 처음부터 끝까지 숫자 2개씩 골라서 더하는 걸로 구했다.

하지만 이렇게 하면 시간이 너무 오래 걸림. O(n^2)

답이 나올 때까지 가능한 모든 2개 조합을 scan하고 있음.

 

그래서 찾아봤더니, unordered map을 사용해서 그 차에 해당하는 값을 O(1)로 구할 수 있다.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> nums_to_find;
        int nums_size = nums.size();
        for(int i = 0; i < nums_size; i++)
        {
            int num_to_find = target - nums[i];
            if(nums_to_find.contains(num_to_find))
            {
                return {nums_to_find[num_to_find], i};
            }
            nums_to_find[nums[i]] = i;
        }
        return {};
    }
};

 

해시 맵을 사용하여 시간 복잡도를 줄일 수 있음.

 

Key Idea

unordered_map을 통해 해시맵 사용.