@@ -0,0 +1,1485 @@
+package array;%0A%0Apublic class Q287FindTheDuplicateNumber %7B%0A%0A    //Difficulty: medium%0A    //TAG: Uber%0A    //TAG: array%0A%0A    /**%0A     * 287. Find the Duplicate Number%0A     * 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.%0A     *%0A     * Example 1:%0A     *%0A     * Input: %5B1,3,4,2,2%5D%0A     * Output: 2%0A     * Example 2:%0A     *%0A     * Input: %5B3,1,3,4,2%5D%0A     * Output: 3%0A     * Note:%0A     *%0A     * You must not modify the array (assume the array is read only).%0A     * You must use only constant, O(1) extra space.%0A     * Your runtime complexity should be less than O(n2).%0A     * There is only one duplicate number in the array, but it could be repeated more than once.%0A     */%0A%0A    /*%0A    Solution:%0A    See https://leetcode.com/problems/find-the-duplicate-number/discuss/72846/My-easy-understood-solution-with-O(n)-time-and-O(1)-space-without-modifying-the-array.-With-clear-explanation.%0A     */%0A%0A    public int findDuplicate(int%5B%5D nums) %7B%0A        if (nums.length %3C= 1) return -1;%0A        int slow = nums%5B0%5D;%0A        int fast = nums%5Bnums%5B0%5D%5D;%0A        while (slow != fast)%0A        %7B%0A            slow = nums%5Bslow%5D;%0A            fast = nums%5Bnums%5Bfast%5D%5D;%0A        %7D%0A%0A        fast = 0;%0A        while (fast != slow)%0A        %7B%0A            fast = nums%5Bfast%5D;%0A            slow = nums%5Bslow%5D;%0A        %7D%0A        return slow;%0A    %7D%0A%0A%7D%0A

287. Find the Duplicate Number