Find the Duplicate Number

解题思路

  1. 这道题很早之前做过，当时没做出来，看了 Solution 后惊为天人，解法再也忘不掉了。

  2. 下面论证下快慢指针找到入口节点的证明。

  3. 设起始点到环入口点距离为 a，环入口点到指针相遇点为 b，指针相遇点回到环入口点为 c；

  4. 则有： 2 * slow(a + b) = fast(a + b + c + b)

  5. 可得： a = c。

代码

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        if (nums.size() < 2) {
            return 0;
        }
        int fast = nums[nums[0]];
        int slow = nums[0];
        while (slow != fast) {
            if (nums[fast] == nums.size() + 1) {
                return 0;
            }
            fast = nums[nums[fast]];
            slow = nums[slow];
        }
        slow = 0;
        while (slow != fast) {
            fast = nums[fast];
            slow = nums[slow];
        }
        return slow;
    }
};