Loading... # Go 题解｜两数之和（Two Sum）：从直觉到 O(n) 的一步步实现 > 给定一个整数数组 `nums` 和一个目标值 `target`，在数组中找出**两**个数，使它们的和等于目标值，并返回这两个数的下标。 --- ## 1. 先从直觉出发：暴力枚举（O(n²)） 思路：用双重循环，枚举所有两两组合，遇到和为 `target` 的就返回。 优点：容易想到、实现简单。 缺点：时间复杂度 O(n²)，当 `n` 很大时会明显变慢。 什么时候用：`n` 很小，或快速验证思路时。 --- ## 2. 换个角度：互补数 + 快速查找（O(1)） 当我们扫描到一个数 `a` 时，另一半就是 `b = target - a`。 关键在于——**如何快速判断 `b` 是否出现过？** 如果使用哈希表（Go 中的 `map`），查找是 O(1)： - 一边遍历数组 - 一边把“见过的数值 → 下标”存到 `map` - 每次看当前 `a`，先查 `map` 里有没有 `b`；有就找到了答案 这样，整体时间复杂度降为 **O(n)**，空间复杂度 **O(n)**。 --- ## 3. 一步步把 O(n) 解法写出来（边查边存） 我们把实现拆成可复盘的 6 步： 1. **准备哈希表** - `hashNums := make(map[int]int, len(nums))` - 用来保存“值 → 该值第一次出现的下标” 2. **遍历数组（从左到右）** - `i` 是当前下标，`num` 是当前值 3. **计算互补数** - `need := target - num` 4. **先查再存（核心顺序）** - 如果 `hashNums[need]` 存在，直接返回 `[hashNums[need], i]` - 反之，将当前值登记：`hashNums[num] = i` 5. **避免用同一个元素两次** - 因为是“先查后存”，即使 `target == 2*num`，也不会把自己当成互补数 6. **遍历完仍未命中** - 返回 `nil`（或按题目要求处理） --- ## 4. 完整代码（含注释与演示） ``` package main import "fmt" // TwoSum 在 nums 中找到和为 target 的两个不同下标并返回。 // 若无解，返回 nil。 func TwoSum(nums []int, target int) []int { // 1) 值 -> 下标 hashNums := make(map[int]int, len(nums)) // 2) 单次遍历，边查边存 for i, num := range nums { // 3) 互补数 need := target - num // 4) 先查 if idx, ok := hashNums[need]; ok { // 找到配对：idx 是先前那个数的下标，i 是当前数的下标 return []int{idx, i} } // 5) 再存当前值的位置（只在没命中时存） hashNums[num] = i } // 6) 无解 return nil } func main() { examples := []struct { nums []int target int }{ {[]int{2, 7, 11, 15}, 9}, // 期望 [0,1] {[]int{3, 2, 4}, 6}, // 期望 [1,2] {[]int{3, 3}, 6}, // 期望 [0,1] {[]int{1, 5, 1, 3}, 6}, // 期望 [0,1] 或 [2,1] {[]int{1, 2, 3}, 100}, // 无解 -> nil } for _, e := range examples { fmt.Printf("nums=%v, target=%d -> %v\n", e.nums, e.target, TwoSum(e.nums, e.target)) } } ``` **运行输出示例（可能根据命中顺序略有不同）：** ``` nums=[2 7 11 15], target=9 -> [0 1] nums=[3 2 4], target=6 -> [1 2] nums=[3 3], target=6 -> [0 1] nums=[1 5 1 3], target=6 -> [0 1] nums=[1 2 3], target=100 -> [] ``` > 说明：当无解时打印的是 `[]`，实际函数返回的是 `nil` 切片，`fmt` 打印会显示为空切片。 --- ## 5. 常见坑与对策 - **先存后查**：会把自己当成互补数，或覆盖更早的下标 → 必须**先查后存** - **把 value 存成值本身**：导致返回的不是下标 → value 必须存**下标** - **提前把所有数都塞进 map 再查**：会覆盖早期下标，且无法保证“最早出现” → 用**单次遍历**解决 - **重复数字**：如 `[3,3]` 且 `target=6`，先查后存可以自然处理 --- ## 6. 复杂度分析 - **时间复杂度**：O(n)（每个元素最多查一次、存一次） - **空间复杂度**：O(n)（最坏情况需要把所有元素都放入哈希表） --- ## 7. 小结 - 暴力法易写但 O(n²)；生产环境下更推荐 **“互补数 + 哈希表”** 的 **O(n)** 解法。 - 代码的关键在于 **“先查后存”** ，这样既避免了使用同一元素两次，也确保返回的是更早出现的下标。  猜你想看 每日一学：PHP 中的array_pad函数详解 PHP函数的定义及使用 每日一学：PHP 中的array_pop函数详解 PHP+Vue实现留言板功能 linux安装企业版宝塔 PHP数据类型 Vue Nuxt3学习-安装 2022年12月9日宝塔严重未知安全性漏洞 给网站更换HarmonySanc字体 PHP学习以及安装 最后修改：2025 年 09 月 25 日 © 允许规范转载 赞 0 如果觉得我的文章对你有用，请随意赞赏
