存在重复元素：见过就记下，再见就真
问的不是「哪两格相等」，而是「当前这个数在左边出现过没有」。集合回答这句话是平均 O(1)。
维护哈希集合 seen，从左扫到右：x 已在集合里则返回 true，否则把 x 放进去。扫完还没有撞见，返回 false。平均时间 O(n)，空间 O(n)。排序后看相邻也能做，时间 O(n log n)，可原地，空间更好。
这是 LeetCode 217. Contains Duplicate。大白话：给你整数数组 nums，只要有某个值出现至少两次就返回 true，每个值都只出现一次就返回 false。
主例 nums = [1, 2, 3, 1]，1 出现在下标 0 和下标 3，返回 true。对照 [1, 2, 3, 4]，四个数彼此不同，返回 false。空数组和单元素都没有重复。
第一反应是两两比较。正确，但 n 到 10⁵ 就超时，而且每个数的取值可以到 10⁹ 量级，不能开计数数组。缺口是「这个值我见过吗」——只需要按值查询，不需要按下标重扫。
问的是值有没有出现过两次
返回值是布尔，不要求给出那两个下标，也不要求统计次数。只要存在一对 i ≠ j 使得 nums[i] == nums[j]。主例那一对是 (0, 3)，值都是 1。
n 最大约 10⁵，值域大约在 ±10⁹。计数数组按值开格会爆内存；按下标两两比会爆时间。后面两条路分别用哈希和排序躲开这两堵墙。
两两比较：每一对都从零开始
对每个 i，让 j 从 i+1 扫到末尾，看 nums[j] 是否等于 nums[i]。主例在 i=0、j=3 时碰上两个 1，返回真。演示第一帧是还没比的数组，第二帧停在下标 3 命中下标 0。
比较次数是 n(n−1)/2。n=10⁵ 时约 5×10⁹ 次，过不了。更糟的是：扫到第二个 1 时，并不记得左边已经见过 1，还得回头把前面每个位置再问一遍。重复是关于过去的事实，暴力却没有过去。
集合：先问在不在，不在再放进去
换一句问法：扫到 x，它在不在已经扫过的那段里？哈希集合 seen 专门回答这个。先查后插：在，就是重复，返回 true；不在，放进去继续。先插后查会把自己当成「已经见过」，每个数都会误报。
用手走主例。下标 0 读到 1，集合空，放进 1。演示第一帧 seen 还是空，正要处理 1。下标 1 读到 2，不在，放进。演示第二帧 seen=[1]。下标 2 读到 3，不在，放进。演示第三帧 seen=[1,2]。下标 3 读到 1，1 已在集合里，返回 true。演示第四帧 seen=[1,2,3]，dup 指向第一次出现的位置 0。对照 [1,2,3,4] 会把四个数都放进去，循环结束返回 false。
平均每次查询、插入 O(1)，整体 O(n)，空间与不同值的个数成正比，最坏 O(n)。值域再大也不影响，哈希按值本身寻址，不按值开数组。
记忆重复是「过去出现过」。集合记住的是值，不是下标。本题不需要下标；若还要求距离不超过 k，那是 LC219，集合要改成窗口。
备选：排序后相等的值必相邻
排序把相同值挤到一起。排完之后只看 nums[i] 与 nums[i+1]，有一对相等就返回 true。主例变成 [1,1,2,3]，第一对相邻就是 1。时间 O(n log n)。若允许改原数组，额外空间 O(1)，这是哈希做不到的。
面试可以两套都讲：要时间用哈希，要原地用排序。不要用计数数组硬扛 10⁹ 的值域。
五行 Go：哈希集合
func containsDuplicate(nums []int) bool {seen := map[int]struct{}{}for _, x := range nums {if _, ok := seen[x]; ok { return true }seen[x] = struct{}{}}return false}
1map[int]struct{} 只当集合用，值不占额外信息。
2先查 ok 再写入。主例前三个数都是不在再放入，第四个 1 走 return true。
3写反成先插入再查，每个 x 都会 ok，答案恒真。
4扫完没有 return，说明全是第一次出现，返回 false。
总结
集合记下见过的值，再见到就真。主例扫到最后的 1 时集合里已有 1。
- 两两比较正确但平方，而且不记得「1 已经出现过」。
- 值域太大不能开计数数组。哈希按值查询，平均 O(n)/O(n)。
- 排序后看相邻是备选，O(n log n)，可原地。