287. 寻找重复数

mid

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

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

示例 1：

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

示例 2：

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

抽象成循环链表问题

本题可以使用数组配合下标，抽象成链表问题，用快慢指针可解

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
func findDuplicate(nums []int) int {
	slow, fast := 0, 0
	for fast != slow || fast == 0 {
		// slow走一步 fast走两步 直到相遇
		slow = nums[slow]
		fast = nums[nums[fast]]
	}

	start := 0 // 设start从头走
	for start != slow {
		start = nums[start]
		slow = nums[slow]
	}
	return slow
}