LeetCode 1. 两数之和题目难度简单题型分类数组、哈希表题目链接两数之和给定整数数组nums和目标值target找出数组中和为target的两个元素返回它们的下标。每组输入恰好有一个有效答案同一个位置不能使用两次答案的下标顺序不限。示例输入nums [2, 7, 11, 15], target 9 输出[0, 1] 输入nums [3, 2, 4], target 6 输出[1, 2] 输入nums [3, 3], target 6 输出[0, 1]数据范围2 nums.length 10^4-10^9 nums[i], target 10^9恰好存在一个有效答案。解题思路使用哈希表记录已经遍历过的“数字 → 下标”。遍历当前数字x时查找target - x是否在哈希表中存在返回它的下标和当前下标。不存在保存当前数字及其下标。先查找再保存避免同一个位置被使用两次。平均时间复杂度O(n)空间复杂度O(n)JavaclassSolution{publicint[]twoSum(int[]nums,inttarget){MapInteger,IntegermnewHashMap();for(inti0;inums.length;i){if(m.containsKey(target-nums[i])){returnnewint[]{m.get(target-nums[i]),i};}m.put(nums[i],i);}returnnewint[]{-1,-1};}}CclassSolution{public:vectorinttwoSum(vectorintnums,inttarget){unordered_mapint,intidx;for(inti0;inums.size();i){autoitidx.find(target-nums[i]);if(it!idx.end()){return{it-second,i};}idx[nums[i]]i;}return{};}};Python 3classSolution:deftwoSum(self,nums:list[int],target:int)-list[int]:dic{}forj,xinenumerate(nums):iftarget-xindic:return[dic[target-x],j]dic[x]jreturn[]
