两数之和-哈希表1-pythonc++

运用哈希表pythonclassSolution(object):deftwoSum(self,nums,target): :type nums: List[int] :type target: int :rtype: List[int] num_indexdict()foridx,numinenumerate(nums):iftarget-numinnum_index:return[idx,num_index[target-num]]num_index[num]idxCclassSolution{public:vectorinttwoSum(vectorintnums,inttarget){// 哈希表思想哈希表key为元素value为index// 一次遍历过程中只要找到当前元素的所需元素在之前遍历到了直接返回结果// 否则添加key-valueunordered_mapint,intnums_index_map;for(inti0;inums.size();i){if(nums_index_map.find(target-nums[i])nums_index_map.end()){nums_index_map[nums[i]]i;}else{return{i,nums_index_map[target-nums[i]]};}}return{};}};复杂度分析时间复杂度O(N)其中 NN 是数组中的元素数量。对于每一个元素 x我们可以 O(1)地寻找 target - num。空间复杂度O(N)其中 NN 是数组中的元素数量。主要为哈希表的开销。