two sums, leetcode-1

two_sum.cpp

#include <iostream>
#include <vector>
#include <map>

using namespace std;

class Solution {
public:
	vector<int> twoSum(vector<int>& nums, int target) {
		multimap<int, int> dict;

		for (int i = 0; i < nums.size(); i++)
		{
			auto delta_num = target - nums[i];
			auto itr = dict.find(delta_num);
			auto count = dict.count(delta_num);
			for (int j = 0; j < count; j++, itr++)
			{
				if (itr->second != i)
				{
					return { i, itr->second };
				}
			}
			dict.emplace(nums[i], i);
		}
		return vector<int>(0);
	}
};

int main()
{
	vector<int> nums;
	nums.push_back(3);
	nums.push_back(2);
	nums.push_back(4);
	nums.push_back(1);
	nums.push_back(3);
	nums.push_back(4);
	nums.push_back(5);
	nums.push_back(6);

	Solution s;
	vector<int> t = s.twoSum(nums, 6);
	for (vector<int>::iterator it = t.begin(); it != t.end(); it++)
	{
		std::cout << *it << std::endl;
	}
}