【LeetCode热题100】【技巧】寻找重复数
题目链接：287. 寻找重复数 - 力扣（LeetCode）
n+1个数的范围在[1,n]，如果以值为下标作为链表指针，没有重复的数也能成环，有重复的数就是这个环有一个数可以由多个地方到达，也就是环有一个入口，这个入口就是重复的数
如：0->1->2->0，加一个重复的数指向2，那么2就是这个环的入口
用快慢指针必会在环里相遇，假设起点到入口的距离是a，入口到相遇的地方距离是b，相遇的地方到入口继续转的距离是c，如果相遇那么快指针比慢指针会多跑一圈，也就是多跑了b+c，而也多走了一倍的距离也就是a+b，那么a=c，此时让一个指针从起点跑a步会到达入口处，一个指针从相遇处跑a步也就是c步也会到达入口处，即重复的数
class Solution {
public:
int findDuplicate(vector<int> &nums) {
int slow = 0, fast = 0;
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);
fast = 0;
while (fast != slow) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
};本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2024-04-07，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
