LeetCode 287. 寻找重复数
题目描述
思路分析
快慢指针问题
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func findDuplicate(nums []int) int {
// 初始化快慢指针
slow, fast := nums[0], nums[0]
// 快慢指针相遇
for {
slow = nums[slow] // 慢指针走一步
fast = nums[nums[fast]] // 快指针走两步
if slow == fast {
break
}
}
// 找到重复的数字
slow = nums[0]
for slow != fast {
slow = nums[slow] // 慢指针走一步
fast = nums[fast] // 快指针走一步
}
return slow
}
- 时间复杂度：
O(n)，快慢指针相遇的时间复杂度是O(n)。- 空间复杂度：
O(1)，只使用了常数级别的空间。
1
write your code here
相似题目
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！