題目鏈接

287.尋找重復數

class Solution {public int findDuplicate(int[] nums) {int low = nums[0];int fast = nums[nums[0]];//1.快慢指針找相遇點while (low != fast) {low = nums[low];fast = nums[nums[fast]];}//2.雙指針找入環點int pre = 0;while (pre != low) {pre = nums[pre];low = nums[low];}return pre;}
}

小結：對nums數組建圖，每個位置i連一條i → nums[i]的邊。由于有且僅有唯一的重復數字target，因此target這個位置一定有起碼兩條指向它的邊，因此整張圖一定存在環，且我們要找到的target就是這個環的入口，那么整個問題就等價于142. 環形鏈表 II。