287. 寻找重复数

快慢指针法

• 分析这个数组，索引从 0 ～ n ，值域是 1 ～ n 。值域，在索引的范围内，值可以当索引使。
• 比如，nums 数组：[4,3,1,2,2]
• 以 nums[0] 的值 4 作为索引，去到 nums[4]
• 以 nums[4] 的值 2 作为索引，去到 nums[2]
• 以 nums[2] 的值 1 作为索引，去到 nums[1]……
• 从一项指向另一项，将 nums 数组抽象为链表：4->2->1->3->2，

/**
 * @param {number[]} nums
 * @return {number}
 */
var findDuplicate = (nums) => {
  let slow = 0
  let fast = 0
  while (true) {
    slow = nums[slow]
    fast = nums[nums[fast]] // slow跳一步，fast跳两步
    if (slow == fast) {
      // 指针首次相遇
      fast = 0 // 让快指针回到起点
      while (true) {
        // 开启新的循环
        if (slow == fast) {
          // 如果再次相遇，就肯定是在入口处
          return slow // 返回入口，即重复的数
        }
        slow = nums[slow] // 两个指针每次都进1步
        fast = nums[fast]
      }
    }
  }
}