算法可视化

哈希表扫描过程

用经典样例观察补数检查和哈希表写入各发生在什么时候。

nums = [2, 7, 11, 15], target = 9

执行轨迹

    题目

    给定一个整数数组 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
    • 三数之和
    • 四数之和