Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution.
Example: Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1]. UPDATE (2016/2/13): The return format had been changed to zero-based indices. Please read the above updated description carefully.
Subscribe to see which companies asked this question 首先对数组进行排序，然后遍历数组，即针对每一个元素，寻找(target-nums[i]), 寻找的方法采用二分法。这样空间复杂度为O(n)(用来记录下标),排序时间复杂度为O(nlogn),遍历数组进行二分查找时间复杂度为O(nlogn)。
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { vector<int> res; vector<int> map(nums); sort(nums.begin(),nums.end()); for(int i = 0;i < nums.size();i++){ int value = target - nums[i]; int left=i+1,right=nums.size()-1; while(left<=right){ int middle = (left+right)/2; if(nums[middle]==value){ for(int j=0;j<map.size();j++){ if(map[j]==nums[i]||map[j]==value) res.push_back(j); } break; } if(value<nums[middle]){ right = middle-1; } else left = middle+1; } if(!res.empty()) break; } return res; } };另外一种想法是利用map，大致思路是遍历一遍数组，将已经访问过的元素存入到map中，再利用value = target - 正在访问的元素，然后回到map中进行查找value。
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { vector<int> res; map<int,int> mp; map<int,int>::iterator it; for(int i=0;i<nums.size();i++){ int find_number = target - nums[i]; it = mp.find(find_number); if(it!=mp.end()){ res.push_back(it->second); res.push_back(i); break; } mp[nums[i]]=i; } return res; } };转载于:https://www.cnblogs.com/GoFly/p/5751070.html
