<p>

287. Find the Duplicate Number

Total Accepted: 33760
Total Submissions: 84769
Difficulty: Hard

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:
You must not modify the array (assume the array is read only).
You must use only constant, O(1) extra space.
Your runtime complexity should be less than O( n^2 )
There is only one duplicate number in the array, but it could be repeated more than once.
Credits:Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.
</p>
<code>

方法一

public class FindtheDuplicateNumber287 {
    public int findDuplicate(int[] nums) {
        int fast=0;
          int slow=0;
        ArrayList<Integer> slowli = new ArrayList<Integer>();
        ArrayList<Integer> fastli = new ArrayList<Integer>();
        while(true){
            slow = nums[slow];
            slowli.add(slow);
            fast = nums[nums[fast]];
            fastli.add(fast);
            if(fast==slow){
                break;
            }
        }
        System.out.println(slowli.toString());
        System.out.println(fastli.toString());
        fast = 0;
        while(true){
            slow = nums[slow];
            fast = nums[fast];
            if(slow == fast){
                break;
            }
        }
        return nums[slow];
    }
    public static void main(String[] args){
     //   int[] nums = {1,5,4,2,1,3,1};
        int[] nums = {2,5,9,6,9,3,8,9,7,1};
        FindtheDuplicateNumber287 fdn = new FindtheDuplicateNumber287();
        int result = -1;
        result = fdn.findDuplicate(nums);
        System.out.println(result);
    }
}

</code>