寻找重复数 - LeetCode 热题 100
大家好！我是曾续缘😝
今天是《LeetCode 热题 100》系列
发车第 100 天
技巧第 5 题
❤️点赞 👍 收藏 ⭐再看，养成习惯
寻找重复数 给定一个包含
n + 1个整数的数组nums，其数字都在[1, n]范围内（包括1和n），可知至少存在一个重复的整数。假设
nums只有 一个重复的整数 ，返回 这个重复的数 。你设计的解决方案必须 不修改 数组
nums且只用常量级O(1)的额外空间。示例 1：
输入：nums = [1,3,4,2,2] 输出：2示例 2：
输入：nums = [3,1,3,4,2] 输出：3示例 3 :
输入：nums = [3,3,3,3,3] 输出：3提示：
1 <= n <= 105nums.length == n + 11 <= nums[i] <= nnums中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次进阶：
难度：💖💖
- 如何证明
nums中至少存在一个重复的数字?- 你可以设计一个线性级时间复杂度
O(n)的解决方案吗？
解题方法
我们可以利用快慢指针的思想来解决这个问题。我们将数组看作一个链表，数组中的元素值对应着链表中的下一个节点的索引。因为数组中存在重复的数字，所以链表一定存在环，我们要找到环的入口即为重复的数字。
- 初始化两个指针 slow 和 fast，初始都指向数组的第一个元素。
- slow 指针每次移动一个位置，fast 指针每次移动两个位置，直到它们相遇在环内的某个位置。
- 一旦两个指针相遇，将其中一个指针重新指向数组的第一个元素，并让它们以相同的速度继续移动，直到它们再次相遇。这次相遇的位置就是环的入口，也就是重复的数字。
Code
public class Solution {public int findDuplicate(int[] nums) {int slow = 0, fast = 0;do {slow = nums[slow];fast = nums[fast];fast = nums[fast];} while (slow != fast);slow = 0;while (slow != fast) {slow = nums[slow];fast = nums[fast];}return slow;}
}