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

运用哈希表

python

classSolution(object):deftwoSum(self,nums,target):""" :type nums: List[int] :type target: int :rtype: List[int] """num_index=dict()foridx,numinenumerate(nums):iftarget-numinnum_index:return[idx,num_index[target-num]]num_index[num]=idx

C++

classSolution{public:vector<int>twoSum(vector<int>&nums,inttarget){// 哈希表思想，哈希表key为元素，value为index// 一次遍历，过程中只要找到当前元素的所需元素在之前遍历到了，直接返回结果// 否则添加key-valueunordered_map<int,int>nums_index_map;for(inti=0;i<nums.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 是数组中的元素数量。主要为哈希表的开销。