一篇文章彻底掌握「两数之和」：Go语言写法最优解法详解

问题描述

「两数之和」是LeetCode上最经典的算法题之一，题目要求：

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

示例：

• 输入：nums = [2, 7, 11, 15], target = 9
• 输出：[0, 1]（因为 nums[0] + nums[1] = 2 + 7 = 9）

2. 算法思路

暴力法（Brute Force）

最直观的方法是双重循环遍历所有可能的组合，时间复杂度 O(n²)，但效率较低。

哈希表优化法（最优解）

利用 哈希表（Hash Map） 存储 值 → 索引 的映射，只需遍历一次数组：

1. 遍历数组，计算 target - nums[i] 是否在哈希表中。
2. 如果在，说明找到了解，直接返回两个索引。
3. 如果不在，把当前 nums[i] 存入哈希表，继续遍历。

时间复杂度：O(n)（只需遍历一次）
空间复杂度：O(n)（需要存储哈希表）

3. 代码解析

修正后的代码

package main

import "fmt"

func twoSum(nums []int, target int) []int {
    m := make(map[int]int)  // 哈希表：存储 值 → 索引 的映射
    for i, v := range nums {
        if k, ok := m[target-v]; ok {  // 检查 target - v 是否在哈希表中
            return []int{k, i}         // 如果存在，返回两个索引
        }
        m[v] = i  // 否则，存入当前值及其索引
    }
    return nil  // 没找到解，返回 nil
}

func main() {
    result := twoSum([]int{2, 7, 11, 15}, 9)
    fmt.Println(result)  // 输出 [0, 1]
}

逐行解析

1. m := make(map[int]int)

   • 创建哈希表 m，用于存储 值 → 索引 的映射。

2. for i, v := range nums

   • 遍历数组 nums，i 是索引，v 是当前值。

3. if k, ok := m[target-v]; ok

   • 检查 target - v 是否在哈希表中：

     • 如果存在 ok = true，说明之前已经存储了一个数 nums[k]，使得 nums[k] + v = target。
     • 直接返回 [k, i]。

4. m[v] = i

   • 如果没找到匹配，就把当前 v 和它的索引 i 存入哈希表，供后续查找。

5. return nil

   • 如果遍历完数组仍然没找到解，返回 nil（Go 里表示空切片）。

6. main() 函数

   • 调用 twoSum 并打印结果。

4. 执行流程（以 nums = [2, 7, 11, 15], target = 9 为例）

最终输出：[0, 1]

5. 复杂度分析

• 时间复杂度 O(n)：只需遍历一次数组，哈希表查找是 O(1)。
• 空间复杂度 O(n)：最坏情况下需要存储所有元素。

6. 边界情况

1. 无解情况

   • 如果 nums = [1, 2, 3], target = 7，返回 nil。

2. 重复元素

   • nums = [3, 3], target = 6 → 返回 [0, 1]（哈希表不会覆盖，因为找到解时直接返回）。

3. 负数 & 零

   • nums = [-1, 0, 1], target = 0 → 返回 [0, 2]。

4. 空数组

   • nums = [], target = 1 → 返回 nil。

7. 总结

• 最优解法：哈希表（O(n) 时间，O(n) 空间）。
• 核心思路：用哈希表存储遍历过的值，避免重复计算。

• Go 实现要点：

  • map[int]int 存储 值 → 索引。
  • if k, ok := m[target-v]; ok 判断是否存在解。
  • main() 不能有返回值，应该打印结果。

这样，这段代码就能高效地解决 Two Sum 问题！ 🚀