C++ 1. Two Sum(Leet Code)

Leet Code_1. Two Sum

 

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

문제 해석

 

이 문제를 풀기위해 이해해야 할 내용은 다음과 같습니다.

 

목표

더해서 target 값이 되는 두개의 원소 찾기

​

방법

1. 더해서 target 값이 되는 두개의 원소 찾기

2. hash map을 사용한다.

 

결과

더해서 target 값이 되는 두개의 원소 찾기

 

통과한 코드

그냥 순회하면서 찾는 코드

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

 

hash map(unordered map)을 사용한 코드

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> res;
        for(int i = 0 ; i < nums.size() ; i++)
        {
            int diff = target - nums[i];
            auto itr = res.find(diff);
            if (itr != res.end()) 
                return {res[diff], i};
            else
                res[nums[i]] = i;
            
        }
        return {};
    }
};

속도가 훨씬 빠르다.

ordered map의 탐색 시간은 O(1)이기 때문인거 같다.(충돌이 안났을 경우)