LeetCode经典题「两数之和」高效哈希解法与工程实践要点

这是一个经典的 **两数之和（Two Sum）** 问题，最优解法是使用 **哈希表（HashMap）** 实现 **O(n) 时间复杂度** 的查找。 --- ### ✅ 解题思路： - 遍历数组，对每个元素 `nums[i]`： - 计算其“补数”：`complement = target - nums[i]` - 检查该补数是否**已存在于哈希表中**（即之前遍历过的某个数）： - 若存在 → 找到答案：返回 `[index_of_complement, i]` - 若不存在 → 将 `nums[i]` 及其下标 `i` 存入哈希表，供后续元素查找 > ⚠️ 注意：题目要求**不能重复使用同一元素**，所以我们是「先查后存」，确保不会匹配到自己。 --- ### ✅ Java 实现（带详细注释）： ```java import java.util.HashMap; import java.util.Map; public class Solution { public int[] twoSum(int[] nums, int target) { // 哈希表：key = 数值，value = 对应下标 Map<Integer, Integer> numToIndex = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int complement = target - nums[i]; // 需要找的另一个数 // 如果补数已存在，说明找到了一对 if (numToIndex.containsKey(complement)) { return new int[]{numToIndex.get(complement), i}; } // 将当前数字及其下标存入哈希表（供后续查找） numToIndex.put(nums[i], i); } // 题目保证有解，此处可不处理，但为健壮性可抛异常 throw new IllegalArgumentException("No two sum solution"); } } ``` --- ### ✅ 示例运行： ```java // 输入： int[] nums = {2, 7, 11, 15}; int target = 9; // 输出： [0, 1] // 因为 nums[0] + nums[1] == 2 + 7 == 9 ``` --- ### 🔍 复杂度分析： | 项目 | 复杂度 | |------|--------| | **时间复杂度** | O(n) —— 单次遍历，哈希表查找/插入平均 O(1) | | **空间复杂度** | O(n) —— 哈希表最多存储 n 个元素 | --- ### ❌ 其他方法对比（简要）： | 方法 | 时间复杂度 | 空间复杂度 | 是否推荐 | 说明 | |------|-------------|----------------|------------|------| | 暴力双重循环 | O(n²) | O(1) | ❌ | 简单但低效，n > 10⁴ 易超时 | | 排序 + 双指针 | O(n log n) | O(n) | ⚠️ | 需额外记录原始下标，较繁琐 | | 哈希表（本解法） | **O(n)** | **O(n)** | ✅✅✅ | **最优、简洁、通用、面试首选** | --- ### 💡 开发建议（来自实战经验）： - 使用 `Map<Integer, Integer>` 而非 `HashMap` 直接声明，更符合面向接口编程原则； - 注意 `nums[i]` 可能为负数或零，哈希表完全支持； - 若题目允许返回**所有解**（不止一对），需改为 `List<int[]>` 并收集全部结果； - 在真实系统中，可加输入校验（如 `nums == null || nums.length < 2`）提升鲁棒性。 ######[AI写代码神器 | 875点数解答 | 2026-03-04 10:19:24]