map、multimap中的find()操作的时间复杂度是O(logn)
unordered_map中find()的时间复杂度是O(1)
alogrithm中的find()的时间复杂度是O(n)
因此本题可以O(nlogn) 这个算法并不是最好的,代码随想录的代码才是神!(我居然还稍微质疑了一下,太菜了..)
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { int len=nums.size(); multimap<int,int>mp; for(int i=0;i<len;i++){ mp.insert(pair(nums[i],i)); } multimap<int,int>::iterator it,itt; vector<int>vec; for(it=mp.begin();it!=mp.end();it++) { int s=target-it->first; itt=mp.find(s); if(itt!=mp.end()&&it!=itt) { vec.push_back(it->second); vec.push_back(itt->second); return vec; } } return vec; } };
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { std::unordered_map <int,int> map; for(int i = 0; i < nums.size(); i++) { // 遍历当前元素,并在map中寻找是否有匹配的key auto iter = map.find(target - nums[i]); if(iter != map.end()) { return {iter->second, i}; } // 如果没找到匹配对,就把访问过的元素和下标加入到map中 map.insert(pair<int, int>(nums[i], i)); } return {}; } };