LeetCode 287 - 寻找重复数

问题描述

给定一个包含 n + 1 个整数的数组 nums，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 中只存在一个重复的整数，但这个重复的整数可能会重复多次，请找出这个重复的整数。

要求：

• 不能修改原数组（假设数组是只读的）。
• 只能使用额外的 O(1) 的空间。
• 时间复杂度小于 O(n^2) 。

示例 1:

输入: nums = [1,3,4,2,2]
输出: 2

示例 2:

输入: nums = [3,1,3,4,2]
输出: 3

示例 3:

输入: nums = [1,1]
输出: 1

示例 4:

输入: nums = [1,1,2]
输出: 1

约束条件:

• 1 <= n <= 10^5
• nums.length == n + 1
• 1 <= nums[i] <= n
• nums 中只有一个整数出现两次或多次，其余整数均只出现一次。

解题思路

这道题的核心难点在于对空间复杂度和时间复杂度的限制，以及不能修改原数组的要求。初看之下，可能会想到用哈希表来记录数字出现的次数，但这样空间复杂度会达到 O(n)。对数组进行排序也不可行，因为题目规定不能修改原数组。

那么，如何在 O(1) 空间复杂度下解决这个问题呢？答案是将此问题巧妙地转化为寻找链表中的环。

核心思想：快慢指针 (Floyd 判圈算法)

我们可以将数组 nums 视为一个链表。数组的下标可以看作是链表节点的“隐式”地址，而数组中存储的值 nums[i] 则可以看作是指向下一个节点的指针（即下一个节点的下标）。

例如，对于数组 nums = [1,3,4,2,2]：

• 我们从下标 0 开始，nums[0] = 1，这意味着从节点 0 跳转到节点 1。
• 当前在下标 1，nums[1] = 3，所以从节点 1 跳转到节点 3。
• 当前在下标 3，nums[3] = 2，所以从节点 3 跳转到节点 2。
• 当前在下标 2，nums[2] = 4，所以从节点 2 跳转到节点 4。
• 当前在下标 4，nums[4] = 2，所以又从节点 4 跳转回了节点 2。

这样，我们就构建了一个以数组下标为节点的序列：0 -> 1 -> 3 -> 2 -> 4 -> 2 -> ...。在这个序列中，节点 2 被重复访问，形成了一个环。

环是如何形成的？
我们将数组的每个索引 i 视为一个节点，而 nums[i] 的值视为从节点 i 出发，指向下一个节点的索引。
由于数组 nums 包含 n + 1 个整数，这些整数的范围是 [1, n]。这意味着数组中的值都可以作为有效的数组下标（题目数值范围 [1,n] 保证了 nums[i] 作为下标不会越界访问 0 到 n 之外的区域，除非 n 非常小，但即使如此，其值也在 [1,n] 内，可作为有效下标）。
我们从索引 0 开始（这可以看作是链表的“头部”或起始探测点），然后根据 nums[当前索引] 不断跳转到下一个索引。
序列可以表示为：x_0 = 0, x_1 = nums[x_0], x_2 = nums[x_1], …, x_{i+1} = nums[x_i]。
由于数组中只有 n+1 个不同的索引（从 0 到 n），而我们通过 nums[x_i] 进行跳转，这个序列最终必然会访问到一个已经访问过的索引，从而形成一个环。这个环的入口点（即第一个被重复访问的索引）就是我们要找的重复数字。

Floyd 判圈算法（也称为龟兔赛跑算法）包含两个主要阶段：

1. 找到相遇点：设置两个指针，一个慢指针 slow，一个快指针 fast。它们都从我们定义的“链表头”（即数组索引 0）开始。

   • slow 每次移动一步：slow = nums[slow] (即 slow 指针更新为其当前指向的数组元素的值，这个值作为下一个索引)。
   • fast 每次移动两步：fast = nums[nums[fast]] (类似地，fast 指针进行两次跳转)。
     如果链表中存在环，fast 指针最终会在环内追上 slow 指针。

2. 找到环的入口：当 slow 和 fast 相遇后，我们将 slow 指针重置回“链表头”（即索引 0）。然后，slow 和 fast 都以每次一步的速度前进 (slow = nums[slow], fast = nums[fast])。它们再次相遇的那个点（索引），就是环的入口，这个索引值也就是我们寻找的重复数字。

算法正确性图解与推导

以 nums = [1,3,4,2,2] 为例：
数组索引作为节点：0, 1, 2, 3, 4
数组值作为指向下一个节点的指针：nums[0]=1, nums[1]=3, nums[2]=4, nums[3]=2, nums[4]=2

形成的路径（索引序列）：
0 --(nums[0]=1)--> 1 --(nums[1]=3)--> 3 --(nums[3]=2)--> 2 --(nums[2]=4)--> 4 --(nums[4]=2)--> 2 ...
这条路径从索引 0 开始，经过 1 和 3 到达 2，然后形成一个环 2 -> 4 -> 2。环的入口点是索引 2。

阶段 1：寻找相遇点
初始时，slow = 0, fast = 0。
根据代码逻辑 (for slow, fast = nums[slow], nums[nums[fast]]; slow != fast; ...)：

1. 首次赋值 (循环初始化部分):
   slow = nums[0] = 1
fast = nums[nums[0]] = nums[1] = 3
   此时 slow = 1, fast = 3。由于 1 != 3，循环继续。

2. 第二次迭代 (循环迭代后部分):
   slow = nums[slow] = nums[1] = 3
fast = nums[nums[fast]] = nums[nums[3]] = nums[2] = 4
   此时 slow = 3, fast = 4。由于 3 != 4，循环继续。

3. 第三次迭代:
   slow = nums[slow] = nums[3] = 2
fast = nums[nums[fast]] = nums[nums[4]] = nums[2] = 4
   此时 slow = 2, fast = 4。由于 2 != 4，循环继续。

4. 第四次迭代:
   slow = nums[slow] = nums[2] = 4
fast = nums[nums[fast]] = nums[nums[4]] = nums[2] = 4
   此时 slow = 4, fast = 4。由于 4 == 4，循环终止。
   快慢指针在索引 4 处相遇。设相遇点为 M，则 M=4。

阶段 2：寻找环的入口
相遇后，slow 被重置为 0，而 fast 保持在相遇点 M=4。
然后两者同步前进，每次一步：

1. slow = nums[slow] = nums[0] = 1
fast = nums[fast] = nums[4] = 2
   此时 slow = 1, fast = 2。由于 1 != 2，循环继续。

2. slow = nums[slow] = nums[1] = 3
fast = nums[fast] = nums[2] = 4
   此时 slow = 3, fast = 4。由于 3 != 4，循环继续。

3. slow = nums[slow] = nums[3] = 2
fast = nums[fast] = nums[4] = 2
   此时 slow = 2, fast = 2。由于 2 == 2，循环终止。
   两者在索引 2 处相遇。这个点就是环的入口 E，所以 E=2。
   函数返回 slow 的值，即 2。这正是 nums = [1,3,4,2,2] 中的重复数字。

为什么此方法能找到重复数字？

设从起点（索引 0）到环的入口点（索引 E）的路径长度为 L。
设环的长度为 C。
当慢指针 slow 和快指针 fast 在环中某点（索引 M）相遇时：
慢指针走过的距离：Dist_slow = L + x (其中 x 是从 E 到 M 沿环方向的距离)
快指针走过的距离：Dist_fast = L + x + k*C (其中 k >= 1 是快指针比慢指针多绕环的圈数)
由于快指针速度是慢指针的两倍，所以 Dist_fast = 2 * Dist_slow。
L + x + k*C = 2 * (L + x)
L + x + k*C = 2L + 2x
k*C = L + x
这意味着 L + x 是环长的整数倍。
我们想找到 L。由上式可得 L = k*C - x。
这个等式告诉我们：从起点 0 走 L 步可以到达环入口 E。同时，从相遇点 M（它距离环入口 E 为 x 步）向前走 L 步，也会到达环入口 E。
这是因为从 M 走 L 步，相当于走了 k*C - x 步。在环上，走 k*C 步等于回到原地，再走 -x 步（即后退 x 步，或者等效于前进 C-x 步，如果 x > 0），都会到达环的入口 E（如果 x=0，则 M 就是 E，走 kC 步也回到 E）。
因此，当一个指针从起点 0 出发，另一个指针从相遇点 M 出发，两者都以相同速度（每次一步）前进时，它们必然会在环的入口点 E 相遇。
这个相遇点 E 是一个索引值。由于题目设定 nums[i] 的值在 [1, n] 范围内，并且这个值被用作下一个索引，那么环的入口索引 E 本身也必须是 [1, n] 范围内的一个值。
如果索引 E 是环的入口，意味着至少有两条不同的“路径”指向了索引 E：一条是首次进入环的路径 (... -> x_{L-1} --(nums[x_{L-1}]=E)--> E)，另一条是环内的路径 (... -> x_{L+C-1} --(nums[x_{L+C-1}]=E)--> E)。由于 x_{L-1} 和 x_{L+C-1} 是不同的索引（除非 L=0，即起点就在环上），但它们指向的下一个索引都是 E (nums[x_{L-1}] = E 且 nums[x_{L+C-1}] = E)，这表明值 E 就是那个被重复指向的数字，即重复数。

再看一个例子：nums = [3,1,3,4,2]。重复数是 3。
路径（索引序列）：0 --(3)--> 3 --(4)--> 4 --(2)--> 2 --(3)--> 3 ...
环是 3 -> 4 -> 2 -> 3。环的入口索引 E = 3。

阶段 1：slow=0, fast=0

1. slow = nums[0]=3, fast = nums[nums[0]]=nums[3]=4. (slow=3, fast=4)
2. slow = nums[3]=4, fast = nums[nums[4]]=nums[2]=3. (slow=4, fast=3)
3. slow = nums[4]=2, fast = nums[nums[3]]=nums[4]=2. (slow=2, fast=2)
   相遇于索引 M=2。

阶段 2：slow=0, fast=2 (相遇点)

1. slow = nums[0]=3, fast = nums[2]=3. (slow=3, fast=3)
   相遇于索引 3。返回 slow，即 3。这正是重复的数字。

实现细节

Go 语言代码直接实现了上述 Floyd 判圈算法。

1. 初始化:
   slow, fast := 0, 0
   两个指针都从索引 0 开始。

2. 阶段 1: 找到相遇点:
   for slow, fast = nums[slow], nums[nums[fast]]; slow != fast; slow, fast = nums[slow], nums[nums[fast]] { }

   • 这个 for 循环的结构比较紧凑：
     • 初始化部分 (仅执行一次): slow 被赋值为 nums[0]，fast 被赋值为 nums[nums[0]]。
     • 条件判断部分: 检查 slow != fast。
     • 循环体: 为空。
     • 迭代后部分: slow 更新为 nums[当前slow]，fast 更新为 nums[nums[当前fast]]。然后回到条件判断。
   • 循环会一直执行，直到 slow 和 fast 指向相同的索引。

3. 阶段 2: 找到环的入口 (即重复数字):
   slow = 0

   • slow 指针被重置回起始索引 0。fast 指针保持在阶段 1 的相遇点。
     for slow != fast {
slow = nums[slow]
fast = nums[fast]
}
   • 此时，slow 和 fast 都以每次一步的速度前进。
   • 当它们再次相遇时，相遇点（一个索引值）就是环的入口，这个索引值也等于重复的数字。

4. 返回值:
   return slow

   • 返回它们在阶段 2 相遇时的索引 slow。

代码实现

这里是题目中提供的 Go 语言解决方案：

package main

/*
 * @lc app=leetcode.cn id=287 lang=golang
 *
 * [287] 寻找重复数
 */

// @lc code=start
func findDuplicate(nums []int) int {
	// 阶段 1: 找到快慢指针的相遇点。
	// 'slow' 和 'fast' 变量代表数组中的索引。
	// 初始时，它们都指向索引 0。
	slow, fast := 0, 0

	// 这个 for 循环的结构：
	// 1. 初始化子句 (只执行一次): slow 指向 nums[0], fast 指向 nums[nums[0]]。
	// 2. 条件子句: slow != fast。如果为真，执行循环体（在此为空），然后执行迭代后子句。
	// 3. 迭代后子句: slow 更新为 nums[当前slow], fast 更新为 nums[nums[当前fast]]。
	// 这个循环会持续直到 slow 和 fast 相遇。
	for slow, fast = nums[slow], nums[nums[fast]]; slow != fast; slow, fast = nums[slow], nums[nums[fast]] {
		// 循环体为空，所有移动逻辑都在 for 语句的头部完成。
	}

	// 阶段 2: 找到环的入口。
	// 将 slow 指针重置回数组的起始位置 (索引 0)。
	// fast 指针保持在阶段 1 中相遇的位置。
	slow = 0
	for slow != fast {
		slow = nums[slow] // slow 从起点开始，每次前进一步。
		fast = nums[fast] // fast 从相遇点开始，每次前进一步。
	}

	// 当 slow 和 fast 再次相遇时，它们所在的索引就是环的入口，
	// 这个索引值也正是题目所求的重复数字。
	return slow
}
// @lc code=end

方法比较

本题主要考察的就是这种 O(1) 空间复杂度的解法。其他可能想到的方法包括：

• 哈希表/集合：遍历数组，将数字存入哈希表。如果数字已存在于哈希表中，则说明找到了重复数。
  • 时间复杂度: O(n)
  • 空间复杂度: O(n) (不符合题目对空间复杂度的要求)
• 排序：对数组进行排序，然后遍历查找相邻且相等的元素。
  • 时间复杂度: O(n log n) (取决于所用排序算法)
  • 空间复杂度: O(1) 或 O(n) (取决于排序算法是否为原地排序，且题目要求不能修改原数组)
• 暴力法：使用双重循环，比较数组中每一对数字是否相等。
  • 时间复杂度: O(n^2) (可能因效率过低而超时，不符合题目对时间复杂度的要求)

方面	快慢指针 (Floyd 算法)	哈希表	排序 + 遍历
时间复杂度	O(n)	O(n)	O(n log n)
空间复杂度	O(1)	O(n)	O(1) 若原地排序*
修改原数组	否	否	是* / 否 (若复制数组)
推荐度	★★★★★ (符合所有要求)	★★☆☆☆ (空间不符)	★★☆☆☆ (修改或时间不优)

注：若要达到 O(1) 空间复杂度，排序通常需要原地进行，这会修改原数组。如果不修改原数组（例如先复制再排序），则空间复杂度为 O(n)。

复杂度分析

• 时间复杂度: O(n)

  • 阶段 1 (找到相遇点): 慢指针 slow 最多走 n 步就会进入环。一旦进入环，快指针 fast 最多在环内比慢指针多走一圈的距离就能追上它。整个过程中，数组中的每个元素（作为索引）最多被访问常数次。因此，此阶段的时间复杂度是 O(n)。
  • 阶段 2 (找到环的入口): slow 从数组头部开始，fast 从相遇点开始，它们都走 L 步（其中 L 是从数组头部到环入口的路径长度）。由于 L <= n，此阶段的时间复杂度也是 O(n)。
  • 总时间复杂度为 O(n) + O(n) = O(n)。

• 空间复杂度: O(1)

  • 算法仅使用了 slow 和 fast 两个额外的整型变量来存储索引。因此，空间复杂度是 O(1)，完全符合题目的要求。

关键收获

• 问题转化能力: 将看似不相关的数组查找问题转化为链表判环问题，是解决本题的核心技巧。这种抽象和建模能力在解决复杂算法问题时至关重要。
• Floyd 判圈算法 (龟兔赛跑算法):
  • 该算法不仅能有效地检测链表中是否存在环，还能精确地定位环的入口点。
  • 它是一种应用广泛的算法，例如在检测单向链表中的循环、某些密码学应用中的序列分析等场景都有应用。
• 数学原理的理解: 深刻理解为什么在第二阶段，一个指针从起点出发，另一个指针从相遇点出发，两者同步前进最终会在环的入口相遇，这需要一定的数学推导（如前文“解题思路”部分所述）。
  • 核心等式：L = k*C - x (其中 L 是从起点到环入口的距离，C 是环的长度，x 是从环入口到快慢指针首次相遇点的距离)。这个关系确保了第二阶段两个指针会在环入口处相遇。
• 关注题目约束: 题目中的限制条件，如“不能修改原数组”、“只能使用 O(1) 的额外空间”，是引导我们找到正确解法方向的关键线索。

这道题目是一道非常经典的面试题，深入理解其解法、背后的数学原理以及如何将问题进行抽象转换，对于提升算法思维和解决问题的能力大有裨益。