Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Note:

  1. You **must not** modify the array (assume the array is read only).
  2. You must use …

455. Sequence analysis

比赛的时候逗了，往看空间限制了....

直接开了个set判重。。。显然MLE 了。。。

然后这道题的正解是 floyd判圈算法（也叫龟兔算法？）

http://www.cnblogs.com/oyking/p/4286916.html  这份题解讲得很详细