sum.cpp

// 2018-02-22

#define METHOD 3

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) 
    {
        int n = nums.size();
        
#if METHOD == 1
        // Naive Brute force solution - first solution I came up with 
        
        for(int i = 0; i < n; ++i)
        {
            for(int j = i+1; j < n; ++j)
            {
                if(nums[i] + nums[j] == target)
                    return {i,j};
            }
        }
#elif METHOD == 2
        // Single pass hashmap
        std::unordered_map<int, int> map; // num value -> num index
        
        for(int i = 0; i < n; ++i)
        {
            int complement = target - nums[i];
            if(map.find(complement) != map.end())
            {
                return {i, map[complement]};
            }
            map[nums[i]] = i;
        }
        
#elif METHOD == 3
        
        using vType = remove_reference_t<decltype(nums)>::size_type;
        std::unordered_map<int,vType> m;
        
        for (int i = 0; i < n; ++i) 
        {
            const auto it = m.find(target - nums[i]);
            if (it != m.end())
                return vector<int> {it->second,i};
            m.emplace(nums[i],i);
        }
#endif
    

        // Fallback
        return {0,0};
    }
};