两数之和

怎样从“给定数组 [2,7,11,15] 和 target=9,返回两个和为 9 的元素下标。”推导出 哈希表 · 边扫边查，并证明每次状态变化都不会漏掉答案？

中心结论：扫描每个元素,先问 map 里有没有补数 target-a[i];命中即配对成功,否则把当前值和下标存入 map。

在数组中找到 2 个数之和等于给定值的数字，结果返回 2 个数字在数组中的下标。

在本站主例中，给定数组 [2,7,11,15] 和 target=9,返回两个和为 9 的元素下标。

算法最终需要得到或观察：下标 [0,1] 的值 2+7=9,即答案。

逐对枚举能够得到答案，但同一个查找会发生许多次；哈希表把已经见过的信息保存成一次查询。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“哈希记忆表”，明确答案需要观察什么。
2. 2状态只维护 哈希表 map(值 → 下标)、扫描指针 i、补数 complement。
3. 3转移每一步按照 扫描每个元素,先问 map 里有没有补数 target-a[i];命中即配对成功,否则把当前值和下标存入 map。
4. 4收尾读取 下标 [0,1] 的值 2+7=9,即答案。，并复核边界与复杂度。

先问未来需要查询什么，再决定 map 的 key 与 value。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：哈希表 map(值 → 下标)、扫描指针 i、补数 complement。

这道题最优的做法时间复杂度是 O(n)。

顺序扫描数组，对每一个元素，在 map 中找能组合给定值的另一半数字，如果找到了，直接返回 2 个数字的下标即可。如果找不到，就把这个数字存入 map 中，等待扫到“另一半”数字的时候，再取出来返回结果。

扫描每个元素,先问 map 里有没有补数 target-a[i];命中即配对成功,否则把当前值和下标存入 map。

执行过程中持续维护：哈希表 map(值 → 下标)、扫描指针 i、补数 complement。

正确性依赖以下不变量：map 里只存放下标 < i 的元素,保证配对的另一半在当前元素之前。

面试时可以压缩为：我用哈希表把暴力 O(n²) 降到 O(n):扫描时先查 map 有没有 target-a[i],命中就返回两个下标,否则把 a[i]→i 存入 map。先查后存避免自己配自己。

落到当前题，执行机制可以压缩为：扫描每个元素,先问 map 里有没有补数 target-a[i];命中即配对成功,否则把当前值和下标存入 map。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入给定数组 [2,7,11,15] 和 target=9,返回两个和为 9 的元素下标。 因为：扫描每个元素,先问 map 里有没有补数 target-a[i];命中即配对成功,否则把当前值和下标存入 map。
2. 2建立空哈希结构目标:找出两个下标,它们的值之和等于 target。 因为：哈希结构把「之前见过什么」变成 O(1) 可查,扫描时即可回头利用历史信息。
3. 3查 map 里有没有 7先不存 a[i],先问 map:有没有等于 7 的值? 因为：未命中,说明之前没有能和它配对的值。
4. 4把 2 → 0 存进 map把当前值和下标存入 map,作为后面元素的「历史记录」。 因为：先查后存,避免一个元素和自己配对。
5. 5预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
6. 6查 map 里有没有 2先不存 a[i],先问 map:有没有等于 2 的值? 因为：命中!2 在 map 里,它和 a[i] 正好凑成 target。
7. 7配对成功 [0, 1]map[2] = 0,与当前 i=1 组成答案。 因为：每个值进 map 前先查补数,保证配对的另一半一定在它之前。
8. 8收尾与复杂度下标 [0,1] 的值 2+7=9,即答案。 因为：时间 O(n) · 空间 O(n)。扫描每个元素,先问 map 里有没有补数 target-a[i];命中即配对成功,否则把当前值和下标存入 map。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

func twoSum(nums []int, target int) []int {
	m := make(map[int]int)
	for k, v := range nums {
		if idx, ok := m[target-v]; ok {
			return []int{idx, k}
		}
		m[v] = k
	}
	return nil
}

func main() {
    // 1. 主例
    //    输入：mode="two-sum", nums=[2,7,11,15], target=9
    //    期望：下标 [0,1] 的值 2+7=9,即答案。
    //
    // 2. 失败 / 未命中
    //    检查：先存后查会让元素与自己配对;必须先查补数再存。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC167 有序数组两数之和(双指针)；LC242 有效字母异位词
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意给定数组 [2,7,11,15] 和 target=9,返回两个和为 9 的元素下标。
2. 2重复逐对枚举能够得到答案，但同一个查找会发生许多次；哈希表把已经见过的信息保存成一次查询。
3. 3优化扫描每个元素,先问 map 里有没有补数 target-a[i];命中即配对成功,否则把当前值和下标存入 map。
4. 4证明map 里只存放下标 < i 的元素,保证配对的另一半在当前元素之前。
5. 5复杂度时间 O(n)，空间 O(n)