问题描述

  1. 包含n+1个整数的数组nums，其数字都在1到n之间，若只存在一个重复的整数，找出这个重复的整数。
  2. https://leetcode-cn.com/problems/find-the-duplicate-number/

解题

  1. 排序，然后遍历数组即可O(nlogn)
  2. 快慢指针可以达到O(n)的时间复杂度
    • 题解中说到之所以将其转换为快慢指针，是因为可以转换为一个链表，但并不是将所有元素都转换为链表！
    • 之所以可以用快慢指针，还因为数组是从0开始的，而且数组中不包括元素0.
    • 之所以可以用快慢指针，是因为那些index和value一样而且还不是重复元素的元素永远不会被遍历到！（从0开始，数组中的其他元素不可能等于该元素）。
    • 之所以可以用快慢指针，还因为重复的元素一定可以被遍历到，
    • 之所以可以用快慢指针，还因为重复的元素是一定存在的！如果不存在重复元素，从0开始的链表依然是一个环，而且所有的元素都在环内。只有那些部分元素在环内的链表才能表示存在重复元素。