[LeetCode/easy] Two Sum (C++)

leetcode.com/problems/two-sum/

Two Sum - LeetCode

새롭게 알게된 점

stl map, unordred_map의 find 함수의 시간복잡도는 log(n), Red Black Tree 기반

 

/* 완전탐색 : O(N^2) */

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

 

/* unordered_map STL 활용 : O(N) */

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> um;
        vector<int> answer;
        for(int i = 0; i < nums.size(); i++) {
            um[nums[i]] = i; // 숫자를 key, 인덱스를 value로 저장
        }
        
        // target에서 현재 수를 뺀 값을 key로 가지고 있는 um이 있는지 확인, 있다면 둘의 합이 target을 의미
        for(int i = 0; i < nums.size(); i++) { 
            int tmp = target - nums[i];
            if(um.find(tmp) != um.end() && um[tmp] != i) {
                answer.push_back(i);
                answer.push_back(um[tmp]);
                break;
            }
        }
        return answer;
    }
};