Two Sum

发布时间:2014-10-22 19:36:53编辑 分享查询网我要评论
本篇文章主要介绍了"Two Sum",主要涉及到Two Sum方面的内容,对于Two Sum感兴趣的同学可以参考一下。

Given an array of integers, find two numbers such that they add up to a specific target number. The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based. You may assume that each input would have exactly one solution. Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2 leetcode 上的第一题,刚开始写了个O(n*n)的解法,结果超时。然后换成hashmap结果WA,是因为有重复值的情况;然后换成了multimap,并学习了一下用法,但还是WA。于是把测试数据拷到本地,调试程序发现是没有处理两个值相等的情况。判断语句改成(valIndexMap.count(second)!=0 && first!=second || valIndexMap.count(second)==2),重新上传,AC。 vector<int> twoSum(vector<int> &numbers, int target) { vector<int> result; unordered_multimap<int, int> valIndexMap; for (int i = 0; i < numbers.size(); i++) { valIndexMap.insert(make_pair(numbers[i], i+1)); } for (auto it = valIndexMap.begin(); it != valIndexMap.end(); it++) { int first = it->first; int second = target - first; if (valIndexMap.count(second)!=0 && first!=second || valIndexMap.count(second)==2) { auto range = valIndexMap.equal_range(second); if (2*first == target) { auto temp = range.first; result.push_back(temp->second); temp++; result.push_back(temp->second); } else { result.push_back(it->second); result.push_back(range.first->second); } sort(result.begin(),result.end()); return result; } } }

上一篇:jdk5 Exchanger 线程之间数据交换
下一篇:漫谈 Clustering (2): k-medoids


关键词: Two Sum