跳转至

LC287 - 寻找重复数

FindTheDuplicateNumber.go
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
package Other

func findDuplicate(nums []int) int {
    slow, fast := 0, 0
    for {
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast {
            break
        }
    }
    fast = 0
    for {
        if slow == fast {
            return slow
        }
        slow = nums[slow]
        fast = nums[fast]
    }
}

本题的关健在于转化为 LC142：

至少存在一个重复的整数 <=> 链表中存在环，找到重复的数 <=> 找到链表入环节点