題目
給定一個包含 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 <= 105
- nums.length == n + 1
- 1 <= nums[i] <= n
- nums 中 只有一個整數 出現 兩次或多次 ，其餘整數均只出現一次
題解
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
# 將尋找數組重複數的問題，轉換成環形鏈表尋找入環節點的問題
# 使用快慢指針的方法實現
slow = nums[0]
fast = nums[0]
# 數組中的元素可以視為指向數組中其他位置的“指針”
while True:
# 起初的疑惑是slow和fast作為索引對應的數值是隨機的，那麼得到的slow和fast是跳躍的。
# 但是你仔細舉個例子畫一畫你會發現，fast就是比slow多走一個“節點”位置，fast走過的slow都會走過
slow = nums[slow] # 這個相當於慢指針走一步
fast = nums[nums[fast]] # 這個相當於快指針走兩步
if slow==fast:
break
# 相遇之後，將快指針置為數組起點
fast = nums[0]
# 每次走一步，當兩個指針再次相遇時，就是入環的節點
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return fast快慢指針的解法，如果存在重複值，那麼鏈表中一定存在環，相遇之後，將快指針置為數組起點，再次相遇就是重複點的位置。
本文章為轉載內容，我們尊重原作者對文章享有的著作權。如有內容錯誤或侵權問題，歡迎原作者聯繫我們進行內容更正或刪除文章。