1两数之和 Java 题解从暴力枚举到哈希表一次遍历给定一个整数数组nums和目标值target找出数组中和为target的两个整数并返回它们的下标。本文分别讲解暴力枚举和哈希表两种解法并给出可直接运行的 Java 代码、测试用例与测试结果。一、题目描述给定一个整数数组nums和一个整数目标值target请在数组中找出和为target的两个整数并返回它们的数组下标。可以假设每种输入只会对应一个答案并且不能重复使用同一个元素。答案可以按任意顺序返回。示例输入nums [2, 7, 11, 15], target 9 输出[0, 1] 解释nums[0] nums[1] 2 7 9约束条件2 nums.length 10^4-10^9 nums[i] 10^9-10^9 target 10^9只存在一个有效答案二、先理解题目的关键点题目要返回的不是两个数字而是它们在数组中的下标。以nums [2, 7, 11, 15]、target 9为例当我们访问数字7时希望快速知道前面是否出现过9 - 7 2。如果出现过直接返回2的下标和7的下标即可。因此这道题的核心问题是如何快速查找一个数字是否已经出现并取得它的下标。三、解法一暴力枚举最容易想到的方法是使用两层循环枚举所有不同的元素组合。publicint[]twoSumBruteForce(int[]nums,inttarget){for(inti0;inums.length;i){for(intji1;jnums.length;j){if(nums[i]nums[j]target){returnnewint[]{i,j};}}}thrownewIllegalArgumentException(不存在符合条件的两个数);}为什么第二层循环从i 1开始避免同一个元素被使用两次避免重复检查(i, j)和(j, i)。暴力解法容易理解但当数组长度达到10^4时最坏情况下要执行接近五千万次比较。时间复杂度O(n²)空间复杂度O(1)四、解法二哈希表一次遍历可以使用HashMap保存已经访问过的数字及其下标数字 - 下标访问当前数字nums[i]时先计算它需要的另一个数complement target - nums[i]然后检查complement是否已经在哈希表中如果存在说明答案已经找到如果不存在把当前数字和下标放入哈希表继续遍历。五、推荐答案Java 哈希表实现importjava.util.HashMap;importjava.util.Map;classSolution{publicint[]twoSum(int[]nums,inttarget){MapInteger,IntegerindexMapnewHashMap();for(inti0;inums.length;i){intcomplementtarget-nums[i];if(indexMap.containsKey(complement)){returnnewint[]{indexMap.get(complement),i};}indexMap.put(nums[i],i);}thrownewIllegalArgumentException(不存在符合条件的两个数);}}为什么要先查询再存入这个顺序可以保证不会重复使用当前元素。例如nums [3, 3], target 6遍历第一个3时哈希表为空查询失败然后存入{30}。遍历第二个3时需要查找的数字也是3哈希表中已经存在下标0于是返回[0, 1]。如果先存再查当前元素可能立刻查到自己违反“不能重复使用同一个元素”的要求。六、执行过程演示以nums [2, 7, 11, 15]、target 9为例当前下标 inums[i]需要查找的数查询前的 HashMap结果027{}未找到存入2 - 0172{20}找到返回[0, 1]整个过程只遍历了数组一次。时间复杂度O(n)空间复杂度O(n)虽然使用了额外空间但时间复杂度从O(n²)降到了O(n)对于长度较大的数组更合适。七、完整可运行代码与测试用例下面的代码可以直接在本地运行同时测试题目给出的三个示例importjava.util.Arrays;importjava.util.HashMap;importjava.util.Map;publicclassTwoSumTest{publicstaticint[]twoSum(int[]nums,inttarget){MapInteger,IntegerindexMapnewHashMap();for(inti0;inums.length;i){intcomplementtarget-nums[i];if(indexMap.containsKey(complement)){returnnewint[]{indexMap.get(complement),i};}indexMap.put(nums[i],i);}thrownewIllegalArgumentException(不存在符合条件的两个数);}privatestaticvoidrunTest(inttestNumber,int[]nums,inttarget,int[]expected){int[]actualtwoSum(nums,target);booleanpassedArrays.equals(actual,expected);System.out.println(测试用例 testNumber);System.out.println(nums Arrays.toString(nums));System.out.println(target target);System.out.println(expected Arrays.toString(expected));System.out.println(actual Arrays.toString(actual));System.out.println(result (passed?PASS:FAIL));System.out.println();}publicstaticvoidmain(String[]args){runTest(1,newint[]{2,7,11,15},9,newint[]{0,1});runTest(2,newint[]{3,2,4},6,newint[]{1,2});runTest(3,newint[]{3,3},6,newint[]{0,1});}}八、测试结果运行结果如下测试用例 1 nums [2, 7, 11, 15] target 9 expected [0, 1] actual [0, 1] result PASS 测试用例 2 nums [3, 2, 4] target 6 expected [1, 2] actual [1, 2] result PASS 测试用例 3 nums [3, 3] target 6 expected [0, 1] actual [0, 1] result PASS三个测试用例全部通过。九、容易踩坑的地方1. 返回数值而不是下标题目要求返回数组下标。正确结果是[0, 1]不是[2, 7]。2. 重复使用同一个元素当nums [3, 2, 4]、target 6时不能把下标0的数字3使用两次。必须选择下标1和2。3. 忽略重复数字nums [3, 3]是一个重要测试用例。哈希表中存储数字和下标可以正确区分两个位置上的3。4. 先存入再查询先存入当前数字可能导致当前元素匹配自己。推荐始终按照“先查询、再存入”的顺序编写。5. 没有答案时返回空数组题目保证存在唯一答案因此在线提交时一定能在循环中返回。为了让独立方法的行为更明确示例在没有答案时抛出异常。十、两种解法对比解法时间复杂度空间复杂度特点暴力枚举O(n²)O(1)容易理解不使用额外集合哈希表O(n)O(n)只遍历一次推荐使用在这道题中哈希表利用额外空间换取更快的查找速度是典型的“空间换时间”。十一、总结“两数之和”虽然是一道简单题却包含了非常典型的算法优化思路暴力枚举检查所有组合时间复杂度为O(n²)哈希表记录已经访问过的数字和下标每次通过target - nums[i]得到需要查找的另一个数哈希表平均可以在O(1)时间完成查找最终把整体时间复杂度优化到O(n)。理解“先查询、再记录”这一步就真正掌握了这道题。更多技术实践与案例可在 【姚前述】中查阅。