find duplicate number

题目链接为https://leetcode.com/problems/find-the-duplicate-number/description/
这道题完全没有正确的思路。网上查了一下，发现这是一道很有名的题目，当年花费了Don Knuth24小时才解出来。
Don Knuth用的是O(n)的算法，使用一个slow指针和fast指针，使用两个while循环，具体的逻辑想了很久也不是十分清楚。有兴趣的同学可以参考一下这篇博客http://bookshadow.com/weblog/2015/09/28/leetcode-find-duplicate-number/
虽说还不是十分理解，这里还是贴出代码

// O(n)
class Solution {
public:
    int findDuplicate (vector<int>& nums) {
        int slow = 0, fast = 0;
        while (true) {
            slow = nums[slow];
            fast = nums[nums[fast]];
            if (slow == fast)
                break;
        }
        int finder = 0;
        while (true) {
            slow = nums[slow];
            finder = nums[finderr];
            if (slow == finder)
                return slow;
        }
    }
};

这道题也有O(n log n)的算法，使用二分查找的思想，具体代码我没有实现。感兴趣的可以参考上面的那篇博客。