力扣解题-两数之和

力扣解题-两数之和

题目：
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]
提示：

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案
进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

Related Topics
数组
哈希表

第一次解答

解题思路

核心方法：哈希表预存全量元素 + 二次遍历查找补值，利用哈希表O(1)的平均查找效率，将时间复杂度从暴力解法的O(n²)优化至O(n)。

具体步骤：

1. 初始化一个HashMap，用于存储数组中的「数值-对应下标」键值对，后续通过数值快速反查下标。
2. 第一次遍历整数数组nums，将数组中所有元素的「数值」作为key、「元素下标」作为value，完整存入HashMap中（注：若存在重复数值，后遍历到的元素下标会覆盖先存入的下标，由于题目保证仅有一个有效答案，该覆盖不影响最终结果）。
3. 第二次遍历整数数组nums，对于当前遍历到的下标i对应的元素nums[i]，计算得到与之匹配的「补值」other = target - nums[i]（即需要找到的另一个和为target的整数）。
4. 校验两个核心条件：①HashMap中包含补值other（存在对应的整数）；②HashMap中补值other对应的下标不等于当前下标i（避免重复使用同一个数组元素）。
5. 若满足上述两个条件，说明找到有效答案，立即将当前下标i和补值other对应的下标封装为结果数组，终止遍历以减少无意义开销。
6. 返回最终结果数组。

提交后耗时5ms

publicint[]twoSum(int[]nums,inttarget){int[]result=null;Map<Integer,Integer>map=newHashMap<>();for(inti=0;i<nums.length;i++){map.put(nums[i],i);}for(inti=0;i<nums.length;i++){intother=target-nums[i];if(map.containsKey(other)&&map.get(other)!=i){result=newint[]{i,map.get(other)};break;}}returnresult;}

第二次解答

解题思路

核心方法：一次遍历 + 边存边查补值，在第一次解答的基础上优化遍历次数，进一步提升实际运行效率，时间复杂度仍为O(n)且执行开销更低。

具体步骤：

1. 初始化一个HashMap，用于存储数组中的「数值-对应下标」键值对，仅存储当前遍历元素之前的数组元素。
2. 仅进行一次遍历整数数组nums，遵循「先查补值，后存当前元素」的逻辑，避免重复匹配：
   a. 对于当前遍历到的下标i对应的元素nums[i]，先计算匹配补值other = target - nums[i]。
   b. 校验两个核心条件：①HashMap中包含补值other；② 补值other对应的下标不等于当前下标i（避免重复使用同一元素）。
   c. 若满足条件，直接封装当前下标i和补值other对应的下标为结果数组，终止遍历。
   d. 若不满足条件，将当前元素的「数值」和「下标」存入HashMap，继续遍历下一个元素。
3. 返回最终结果数组。

核心优化点说明：

• 合并两次遍历为单次遍历，减少了数组的整体访问次数，是耗时从5ms降至2ms的关键。
• 「边存边查」仅存储前置元素，既保证了有效答案的匹配（两个答案元素必然一前一后出现），又避免了第一次解答中后续元素覆盖前置元素下标的潜在问题，逻辑更严谨。

提交后耗时2ms

publicint[]twoSum(int[]nums,inttarget){int[]result=null;Map<Integer,Integer>map=newHashMap<>();for(inti=0;i<nums.length;i++){intother=target-nums[i];if(map.containsKey(other)&&map.get(other)!=i){result=newint[]{i,map.get(other)};break;}map.put(nums[i],i);}returnresult;}

总结

1. 两次解答均采用「哈希表」实现快速查找，核心思想是「时间换空间」，将查找效率从O(n)优化至O(1)，整体时间复杂度均为O(n)。
2. 第一次解答是「预存全量元素 + 二次查找」，逻辑简单直观；第二次解答是「单次遍历 + 边存边查」，优化了遍历次数，实际运行效率更高。
3. 两次解答均遵循「避免重复使用同一元素」的核心约束，且满足题目「任意顺序返回答案」的要求。