寻找重复数
Find the Duplicate Number
题目详情
问题：寻找重复数
考察：数组、双指针、二分查找
来源：DSA Prep / Citadel
链接：https://leetcode.com/problems/find-the-duplicate-number
英文原题
Problem: Find the Duplicate Number
Patterns: Array, Two Pointers, Binary Search
Recency: 6mo
Link: https://leetcode.com/problems/find-the-duplicate-number
Source: https://www.dsaprep.dev/blog/citadel-coding-interview-questions/
解析
思路：把数组值看作从下标指向下一个下标的函数，重复数会形成环入口。使用 Floyd 快慢指针先相遇，再从起点和相遇点同步前进找到环入口。
复杂度：时间 O(n)，空间 O(1)，且不修改数组。
英文解析
Approach: Treat `nums[i]` as a pointer to the next index. Because one value is duplicated, the functional graph has a cycle; Floyd’s slow/fast pointers find the cycle entrance, which is the duplicate.
Complexity: Time , space .