Python 查找重复元素：双指针法实现

这篇文章将介绍使用双指针法来查找数组中重复元素的 Python 代码实现。

问题描述： 给定一个包含 n + 1 个整数的数组 nums，其中每个整数都在 1 到 n 之间（包括 1 和 n），且至少存在一个重复的数字。你需要找出数组中任意一个重复的数字。

双指针法

双指针法是一种常见的算法技巧，它使用两个指针来遍历数组或链表，从而达到特定目的。在这个问题中，我们使用两个指针：slow 和 fast，它们都从数组的第一个元素开始。

slow 指针每次移动一步，fast 指针每次移动两步。当 slow 和 fast 指针相遇时，说明数组中存在循环。然后，我们重置 fast 指针到数组的第一个元素，并让 slow 和 fast 指针以相同的速度移动，直到它们再次相遇。此时，slow 指针指向的就是数组中重复的元素。

Python 代码实现：

def findDuplicate(nums):
    slow = nums[0]
    fast = nums[0]
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break
    fast = nums[0]
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    return slow

print(findDuplicate([1, 3, 4, 2, 2]))

代码解析：

slow 和 fast 指针初始化为数组的第一个元素。
循环遍历数组，slow 指针每次移动一步，fast 指针每次移动两步。
当 slow 和 fast 指针相遇时，说明数组中存在循环。此时，fast 指针被重置为数组的第一个元素，slow 和 fast 指针以相同的速度移动。
当 slow 和 fast 指针再次相遇时，slow 指针指向的就是数组中重复的元素。

示例：

print(findDuplicate([1, 3, 4, 2, 2]))  # 输出 2

总结：

本文介绍了使用双指针法查找数组中重复元素的 Python 代码实现，并提供了详细的代码解析和示例。双指针法是一种灵活的算法技巧，可以用于解决多种问题。