287. Find the Duplicate Number

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 only constant. O(1) extra space.
3. Your runtime complexity should be less than O(n2).
4. There is only one duplicate number in the array, but it could be repeated more than once.

Approach:

To understand this problem, you must first understand problem 142:https://blog.jing.do/5371。

Think of this array as a linked list. There are two pointers, a fast pointer and a slow pointer. If there are no duplicates, they will never meet. If there are duplicates, the fast pointer will get stuck and wait for the slow pointer to meet.

Once encountered, iterate from the beginning (last or first) to find the intersection of the two values, which will be the duplicates.

If it's hard to understand, start by understanding 142.

class Solution { public int findDuplicate(int[] nums) { int slow = nums[nums.length-1]; int fast = nums[nums[nums.length-1]-1]; while(slow != fast){ slow = nums[slow-1]; fast = nums[nums[fast-1]-1]; } slow = nums.length; while(slow != fast){ slow = nums[slow-1]; fast = nums[fast-1]; } return slow; } }