寻找重复数

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)，且不修改数组。