题目

给定一个整数数组 nums 和目标值 target，找出两个下标，使得对应元素之和等于 target。

题目分析

这道题很适合作为算法题解入门题，因为它的优化路径非常直白：

  • 先想到最直接的双重循环
  • 再思考怎样避免重复查找
  • 最后自然过渡到哈希表

核心问题其实只有一个：当我们遍历到当前数字时，能不能立刻知道它需要的“另一个数”是否已经出现过。

方法一：直觉解法

最直接的写法就是枚举所有二元组。

 1func twoSumBruteForce(nums []int, target int) []int {
 2    for i := 0; i < len(nums); i++ {
 3        for j := i + 1; j < len(nums); j++ {
 4            if nums[i]+nums[j] == target {
 5                return []int{i, j}
 6            }
 7        }
 8    }
 9    return nil
10}

这个方法容易理解，但时间复杂度是 O(n^2)。

方法二：优化思路

如果我们在遍历到 nums[i] 时，已经知道前面每个数字出现过的位置，那么只要算出 target-nums[i]，就能马上判断答案是否已经出现过。

这正好对应哈希表：

  • key：数值
  • value：下标

Go 实现

 1func twoSum(nums []int, target int) []int {
 2    indexByValue := make(map[int]int, len(nums))
 3    for i, num := range nums {
 4        need := target - num
 5        if j, ok := indexByValue[need]; ok {
 6            return []int{j, i}
 7        }
 8        indexByValue[num] = i
 9    }
10    return nil
11}

复杂度分析

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

易错点

  • 一定要先查哈希表，再插入当前值，避免把同一个元素使用两次
  • 如果题目要求返回的是下标，map 的 value 应该存位置，而不是计数

我的复盘

这题最大的价值，不是哈希表本身，而是让我再次确认了一件事：很多优化并不复杂，关键是把“重复做的事”显式找出来。

关联题

  • 两数之和 II
  • 三数之和
  • 四数之和