【代码随想录笔记】哈希表篇

🟠 LeetCode 1. 两数之和

🧠 思路总结（最佳解法）

✅ 方法：使用哈希 Map 存储目标差值

• 遍历数组时，计算当前值 nums[i] 对应的目标配对值 target - nums[i]；

• 使用一个 Map 记录之前遍历过的数字及其下标；
• 如果当前值已经在 Map 中存在，说明找到了匹配的一对；
• 否则将 (target - nums[i], i) 存入 Map，供后续查找；

⏱️ 复杂度分析

• 时间复杂度：O(n)
只需遍历数组一次，每个元素只处理一次

• 空间复杂度：O(n)
最坏情况下所有元素都存入 Map

✅ 推荐写法（标准答案风格）

✅ 方法三：排序 + 双指针（进阶思路 TODO）

• 先对数组排序并记录原始索引；

• 然后使用双指针从两端向中间逼近目标值；

• 时间复杂度 O(n log n)，空间复杂度 O(n)

⚠️ 注意：排序会打乱原数组顺序，返回原始下标时需要额外处理

💬 面试要点

• 能讲清楚为什么要用哈希表
• 查找配对数的时间复杂度从 O(n) 降为 O(1)

• 能主动分析复杂度

🟠 LeetCode 454. 四数相加 II

🧠 思路总结（最佳解法）

✅ 方法：分组 + 哈希 Map 优化

• 将四数组两两分组：
• A 和 B 一组，C 和 D 一组；

• 第一步计算所有 A[i] + B[j] 的和，并记录出现次数到哈希表中；

• 第二步遍历所有 C[k] + D[l] 的和，查找是否存在相反数（即 (C[k]+D[l])）；

• 若存在，则加上对应的组合数量；

⏱️ 复杂度分析

• 时间复杂度：O(n²)
• 每个数组两两组合共 n × n = n² 种情况
• 不会退化为更高阶复杂度

• 空间复杂度：O(n²)
• 最坏情况下所有 A[i] + B[j] 的和都不同，需要存储 n² 项

✅ 推荐写法（标准答案风格）

💡 面试要点

• 能讲清楚为什么要分组
• 减少暴力枚举的复杂度（从 O(n⁴) 到 O(n²)）

• 能主动分析复杂度

📌 总结一句话：

本题的核心是“降低暴力枚举的复杂度”，使用哈希 Map 分组统计是一种经典套路，适合面试表达。