力扣 “两数之和” 最优解：哈希表 O (n) 时间复杂度实现详解

大家好，今天来讲解力扣经典入门题「两数之和」，分享如何用哈希表实现时间复杂度 O (n) 的高效解法。

一、题目回顾

给定整数数组nums和目标值target，找出数组中和为 target 的两个整数，返回它们的下标。

• 假设输入只有一个答案
• 不能使用同一个元素两次

二、暴力解法的问题

最直观的思路是双重循环遍历数组（时间 O (n²)），但数据量大时效率很低。

三、哈希表优化解法（我的代码）

利用哈希表存储 “数值 - 下标”，遍历数组时直接查找target - 当前数是否存在，实现一次遍历完成查找：

class Solution { public int[] twoSum(int[] nums, int target) { Map<Integer,Integer> map=new HashMap<>(); // 遍历数组 for(int i=0;i<nums.length;i++){ // 计算需要找的互补数 int complement = target - nums[i]; // 若互补数已在哈希表中，直接返回下标 if(map.containsKey(complement)){ return new int[]{map.get(complement),i}; } // 否则将当前数和下标存入哈希表 map.put(nums[i],i); } // 题目保证有解，这里仅为语法要求 return new int[0]; } }

四、代码逻辑拆解

1. 初始化哈希表：HashMap用来存已经遍历过的元素（键是数值，值是下标）。
2. 遍历数组：
   • 计算当前数的互补数：complement = target - nums[i]。
   • 检查哈希表中是否有这个互补数：
     • 有 → 直接返回 “互补数的下标” 和 “当前下标”。
     • 没有 → 把当前数和下标存入哈希表，继续遍历。
3. 返回结果：题目保证有解，所以循环内一定会 return。

五、复杂度分析

• 时间复杂度：O (n)（仅遍历一次数组，哈希表查找是 O (1)）。
• 空间复杂度：O (n)（最坏情况需要存储 n-1 个元素到哈希表）。

这个解法是「两数之和」的最优解之一，既简洁又高效，非常适合入门学习哈希表的应用～