LeetCode 287. Find the Duplicate Number

Question

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and uses only constant extra space.

https://leetcode.com/problems/find-the-duplicate-number/

• Solution1

class Solution {
    public int findDuplicate(int[] nums) {
        //Set<Integer> seen = new HashSet<>();
        //for(int num : nums)
        //    if(!seen.add(num)) return num;
        //return -1;
        int slow = nums[0], fast = nums[0];
        while(true){
            slow = nums[slow];
            fast = nums[nums[fast]];
            if(slow == fast){
                fast = nums[0];
                while(fast != slow){
                    slow = nums[slow];
                    fast = nums[fast];
                }
                return slow;
            }
        }
    }
}

Complexity:

Time complexity: O(n)

Space complexity: O(1)