LeetCode 287：快慢指针巧解重复数

LeetCode287给定一个包含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]输出3Python解法1.二分查找class Solution: def findDuplicate(self, nums: List[int]) - int: left 1 right len(nums) - 1 while left right: mid (left right) // 2 cnt 0 for num in nums: if num mid: cnt 1 if cnt mid: right mid else: left mid 1 return left2.快慢指针class Solution: def findDuplicate(self, nums: List[int]) - int: slow fast 0 # 第一阶段快慢指针不同速环内相遇 while True: slow nums[slow] fast nums[nums[fast]] if slow fast: break # 第二阶段slow重置起点同速找环入口 slow 0 while slow ! fast: slow nums[slow] fast nums[fast] return slowJava解法1.二分查找class Solution { public int findDuplicate(int[] nums) { int left 1; int right nums.length - 1; int mid 0; int cnt 0; while(left right){ mid (left right) / 2; cnt 0; for(int num : nums){ if(num mid){ cnt; } } if(cnt mid){ right mid; }else{ left mid 1; } } return left; } }2.快慢指针public int findDuplicate(int[] nums) { int slow 0, fast 0; // 1.快慢指针不同速直到环内相遇 do { slow nums[slow]; // 走1步 fast nums[nums[fast]]; // 走2步 } while (slow ! fast); // 2.慢指针放回起点二者同速前进 slow 0; while (slow ! fast) { slow nums[slow]; fast nums[fast]; } return slow; }C解法1.二分查找class Solution { public: int findDuplicate(vectorint nums) { int left 1; int right nums.size() - 1; int mid 0; int cnt 0; while(left right){ mid (left right) / 2; cnt 0; for(int num : nums){ if(num mid){ cnt; } } if(cnt mid){ right mid; }else{ left mid 1; } } return left; } };2.快慢指针#include vector using namespace std; class Solution { public: int findDuplicate(vectorint nums) { int slow 0, fast 0; // 第一步快慢指针相遇 do { slow nums[slow]; fast nums[nums[fast]]; } while (slow ! fast); // 第二步同速前进找入口 slow 0; while (slow ! fast) { slow nums[slow]; fast nums[fast]; } return slow; } };快慢指针快慢指针核心优势仅 O (1) 额外空间一次 / 两次遍历完成无需额外容器分为「快慢步速差指针」「前后同步快慢指针」两大类。场景 1链表判环、找环入口Floyd 龟兔算法适用题目LeetCode141 环形链表判断链表是否存在环LeetCode142 环形链表 II找到环的起始节点LeetCode287 寻找重复数数组映射为带环链表思路快指针一次走 2 步慢指针一次 1 步有环必相遇再同速找入口。场景 2链表 / 数组找中点、倒数第 k 个节点1找链表中点LeetCode876 链表的中间结点slow 走 1 步fast 走 2 步fast 走到末尾时slow 刚好在中点。2倒数第 k 个节点LeetCode19 删除链表倒数第 N 个结点快指针先提前走 k 步再快慢同速向后走fast 到末尾时 slow 指向倒数第 k 个。场景 3原地数组分区、移动元素如 LeetCode283 移动零slow 记录下一个合法元素存放位置fast 遍历数组fast 找到符合条件元素时和 slow 交换 / 覆盖slow 前进。 类似题目移除元素、颜色分类。场景 4链表判回文LeetCode234快慢指针找到链表中点反转后半段再前后指针同步比对。场景 5链表奇偶重排、拆分链表用快慢指针分割链表为前后两部分再重组。场景 6滑动窗口类优化快慢指针 / 滑动窗口双指针slow 为窗口左边界fast 为右边界满足条件收缩左边界常用于子数组求和、最长无重复子串等。局限仅适用于线性结构链表、可映射为链表的数组环形问题需要数学推导理解逻辑门槛高于二分、哈希无法处理多环、多入口复杂结构仅单环单入口场景。