首页 > 代码库 > [LeetCode] TwoSum
[LeetCode] TwoSum
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
妈妈我再也不敢装逼了，本以为三分钟可以秒杀的题做了三小时！心想暴力O(n^2)肯定是过不了的，然后脑子里飘来4个字“二分查找”，然后我就写啊写，写好了二分找发现这题返回的不是数啊，是原数组的index啊，这下麻烦了，因为二分找要排序，排完序索引不就丢了嘛，没办法只能copy一次原数组然后用二分找找出值来在遍历一遍原始数组找索引，弄来弄去做了很长时间才AC，最后网上发现简单的解法：排序然后从两头向中间找。。。
要注意几点就是：1.返回的是索引，不是数。 2.允许出现重复
int bfind(vector<int> &numbers, int left, int right, int target, int exclu) { if (left > right) return -1; int mid = (left + right)/2; if (target > numbers[mid]) { return bfind(numbers, mid + 1, right, target, exclu); } else if (target < numbers[mid]) { return bfind(numbers, left, mid - 1, target, exclu); } else { if (mid != exclu) { return numbers[mid]; } return -1; }}vector<int> twoSum(vector<int> &numbers, int target) { vector<int> ret; vector<int> aux = numbers; sort(numbers.begin(), numbers.end()); // O(nlogn) for (int i = 0; i < aux.size(); i++) { int j = bfind(numbers,0, (int)numbers.size()-1, target-numbers[i], i); if (j >= 0) { for (int k = 0; k < aux.size(); k++) { if (aux[k] == numbers[i]) { ret.push_back(k+1); } else if (aux[k] == j) { ret.push_back(k+1); } } return ret; } } return ret;}
网上有更简单的版本，这个就仅供娱乐吧。
[LeetCode] TwoSum
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。