[Hashing][Easy] 1. Two Sum

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

 

Q. 주어진 정수 배열에서 두 합이 target이 되는 두 index를 반환하라. 

 

 

Solution.

 많이 나오는 패턴의 문제. 

 값을 키로 하고 위치를 바로 접근 가능하도록 해시화 하는 것이 문제 풀이의 핵심. 

 

 문제 자체에 제한이 있으므로, 중복키는 마지막 위치로 대처해도 로직은 정상 작동.

 

vector<int> twoSum(vector<int>& nums, int target) 
{
    unordered_map<int, int> mapPos;
    for(int q = 0; q < nums.size(); ++q)
        mapPos[ nums[q] ] = q;

    vector<int> vRet;
    for(int q = 0; q < nums.size(); ++q)
    {
        int diff = target - nums[q];
        if(mapPos.find(diff)!=mapPos.end() && q!=mapPos[diff])
        {
            vRet.push_back(q);
            vRet.push_back( mapPos[diff] );
            return vRet;
        }
    }
    return vRet;
}

 

결과.