摘要
在数组中找出唯一的重复数字，听起来像一道简单的题目，但如果你不能修改原数组、不能使用额外空间，挑战就变得很有意思了。本文通过 Swift 实现 LeetCode 第 287 题《寻找重复数》的题解，并结合实际编码场景详细拆解背后的逻辑推理过程，帮你真正掌握这道经典的算法题。
描述
题目要求你在一个包含 n + 1 个整数的数组中找到一个重复的数。这些数的取值范围是 [1, n]，而且保证 只有一个数字重复，可能重复多次。
但它还加了一些限制：
- 数组不能修改（也就是只读）
- 空间复杂度得是常数级 O(1)
- 尽可能做到时间复杂度为线性 O(n)
看起来挺棘手？别急，下面我们一步一步来拆解。
题解答案
常见的思路有三种：
- 暴力法 / 哈希法（不能用，违反空间复杂度）
- 排序 + 遍历（不能用，违反不能修改数组）
- 快慢指针（可以用，经典的“链表找环”变体）
我们要用的是第三种方法，也叫 Floyd 判圈算法。
思路是把数组元素看成指针，nums[i] 代表指向下一个元素的索引，就像一个链表。如果有重复数字，就一定会有一个“环”。
题解代码分析
func findDuplicate(_ nums: [Int]) -> Int {
var slow = nums[0]
var fast = nums[0]
// 第一阶段：找相遇点
repeat {
slow = nums[slow]
fast = nums[nums[fast]]
} while slow != fast
// 第二阶段：找入口（重复的数字）
slow = nums[0]
while slow != fast {
slow = nums[slow]
fast = nums[fast]
}
return slow
}
解读：
- 第一次
while循环找的是两个指针在环里相遇的那个位置。我们先从nums[0]开始，slow每次走一步，fast每次走两步，像跑圈一样，最终肯定会在环里相遇。 - 第二次
while循环是经典的“找环入口”，我们让一个指针从开头出发，另一个从相遇点出发，每次走一步，再次相遇的点就是重复数字。
示例测试及结果
let test1 = [1, 3, 4, 2, 2]
print(findDuplicate(test1)) // 输出: 2
let test2 = [3, 1, 3, 4, 2]
print(findDuplicate(test2)) // 输出: 3
let test3 = [3, 3, 3, 3, 3]
print(findDuplicate(test3)) // 输出: 3
无论重复的是谁，只要有重复，这个算法就能找出来，效率也很高。
时间复杂度
- 整体是 O(n)，因为我们最多只跑两次遍历，而且每次最多走 n 步。
空间复杂度
- O(1)，只用了两个变量
slow和fast，没有开任何额外空间。
总结
这题乍一看像是“简单查重”，实则考验对链表结构与指针遍历逻辑的理解。如果你碰到限制不能修改数组、不能用额外空间的情况，这种借助“指针构造隐含链表”的技巧就非常值得掌握。
而且这种技巧在很多系统设计里也很实用，比如检测日志流的循环引用、追踪用户路径中的重复操作等等。
实际场景类比
想象一下你在做用户路径分析，用户访问路径用数组表示 [页面1, 页面2, 页面3, 页面2, 页面4]，你希望知道哪个页面用户又返回访问了。
你不能改动原始日志（只读），也不能复制一份数据再做处理（节省内存），这时候就可以考虑类似的“快慢指针找环”方式来识别重复跳转的路径。
可运行 Demo（Swift Playground）
import Foundation
func findDuplicate(_ nums: [Int]) -> Int {
var slow = nums[0]
var fast = nums[0]
repeat {
slow = nums[slow]
fast = nums[nums[fast]]
} while slow != fast
slow = nums[0]
while slow != fast {
slow = nums[slow]
fast = nums[fast]
}
return slow
}
let sample = [1, 4, 6, 2, 5, 3, 6]
print("重复数字是：\(findDuplicate(sample))")
未来展望
这个题是很多“限制场景下查重”的代表题，我们可以往更复杂的方向去探索：
- 如何在海量数据（分布式系统）中查找重复？
- 如果有多个重复的数字，又该如何扩展这类算法？
- Swift 中的指针式遍历，还有哪些地方能发挥类似作用？