- 题目要求
O(1)
空间,因此不能用哈希表。将i
与nums[i]
视为链表的相邻节点,如果nums[i]
存在重复元素,则该链表有环
nums[i] = 1 3 4 2 2
i = 0 1 2 3 4
nums[0] = 1
nums[1] = 3
nums[3] = 2
nums[2] = 4
nums[4] = 2
nums[2] = 4
nums[4] = 2
陷入循环
- 用快慢指针找环入口即可
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int slow = 0;
int fast = 0;
while (true) {
slow = nums[slow];
fast = nums[nums[fast]];
if (slow == fast) {
break;
}
}
fast = 0;
while (slow != fast) { // 找环入口
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
};