Two Sum

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

일반적으로는 for문 2번 도는 O(N^2) 방법을 생각한다. 이때 해시를 이용해서 a+b=c이라고 할때 a를 해시에 넣기 전에 먼저 b(c-a)가 있는지 확인한다. 이 방법으로 O(N)으로 해결가능하다.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int,int> hash;
        vector<int> ret(2);
        int len=nums.size();
        for(int i=0;i<len;i++)
        {
            auto it=hash.find(target-nums[i]);
            if(it!=hash.end())
            {
                ret[0]=i;
                ret[1]=it->second;
                return ret;
            }
            hash.insert({nums[i],i});
        }
    }
};