存在重复元素

怎样从“给定数组 [1,2,3,1],判断是否存在重复元素。”推导出 哈希集合 · 去重，并证明每次状态变化都不会漏掉答案？

中心结论：用一个 set 记录见过的值;扫描时若当前值已在 set 中即存在重复。

这是一道简单题，如果数组里面有重复数字就输出 true，否则输出 flase。

在本站主例中，给定数组 [1,2,3,1],判断是否存在重复元素。

算法最终需要得到或观察：扫到第二个 1 时命中,返回 true。

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

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

1. 1建模把输入翻译成“哈希记忆表”，明确答案需要观察什么。
2. 2状态只维护 哈希集合 set(已见过的值)、扫描指针 i。
3. 3转移每一步按照 用一个 set 记录见过的值;扫描时若当前值已在 set 中即存在重复。
4. 4收尾读取 扫到第二个 1 时命中,返回 true。，并复核边界与复杂度。

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

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：哈希集合 set(已见过的值)、扫描指针 i。

用一个 set 记录见过的值;扫描时若当前值已在 set 中即存在重复。

执行过程中持续维护：哈希集合 set(已见过的值)、扫描指针 i。

正确性依赖以下不变量：set 始终等于下标 [0, i) 出现过的值的集合。

面试时可以压缩为：我边扫边用 set 记录见过的值,扫到已在 set 中的值就立刻返回 true;扫完没命中返回 false,O(n)。

落到当前题，执行机制可以压缩为：用一个 set 记录见过的值;扫描时若当前值已在 set 中即存在重复。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入给定数组 [1,2,3,1],判断是否存在重复元素。 因为：用一个 set 记录见过的值;扫描时若当前值已在 set 中即存在重复。
2. 2set 里有没有 1查 set 是否已经包含 a[i]。 因为：未命中,说明该值首次出现。
3. 3把 1 加入 set把新值加入 set,作为后续比对的历史。 因为：扫到末尾都没命中,才能确定没有重复。
4. 4set 里有没有 2查 set 是否已经包含 a[i]。 因为：未命中,说明该值首次出现。
5. 5把 2 加入 set把新值加入 set,作为后续比对的历史。 因为：扫到末尾都没命中,才能确定没有重复。
6. 6把 3 加入 set把新值加入 set,作为后续比对的历史。 因为：扫到末尾都没命中,才能确定没有重复。
7. 7set 里有没有 1查 set 是否已经包含 a[i]。 因为：命中即可立刻返回 true,无需扫完。
8. 8收尾与复杂度扫到第二个 1 时命中,返回 true。 因为：时间 O(n) · 空间 O(n)。用一个 set 记录见过的值;扫描时若当前值已在 set 中即存在重复。

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

func containsDuplicate(nums []int) bool {
	record := make(map[int]bool, len(nums))
	for _, n := range nums {
		if _, found := record[n]; found {
			return true
		}
		record[n] = true
	}
	return false
}

func main() {
    // 1. 主例
    //    输入：mode="contains-duplicate", nums=[1,2,3,1]
    //    期望：扫到第二个 1 时命中,返回 true。
    //
    // 2. 失败 / 未命中
    //    检查：命中后仍继续扫是浪费;一旦命中可立即返回。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC1 两数之和；LC242 有效字母异位词
}

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

1. 1题意给定数组 [1,2,3,1],判断是否存在重复元素。
2. 2重复逐对枚举能够得到答案，但同一个查找会发生许多次；哈希表把已经见过的信息保存成一次查询。
3. 3优化用一个 set 记录见过的值;扫描时若当前值已在 set 中即存在重复。
4. 4证明set 始终等于下标 [0, i) 出现过的值的集合。
5. 5复杂度时间 O(n)，空间 O(n)