287. Find the Duplicate Number

原题：287. Find the Duplicate Number

这道题限制了时间复杂度不能超过O(n^2)，空间复杂度不能超过O(1)，且不能修改原数组，这样可以使用的方法就非常有限了。

解题思路和142. Linked List Cycle II一样使用快慢指针。

source code

// Runtime: 72 ms, faster than 48.84% of JavaScript online submissions for Find the Duplicate Number.
// Memory Usage: 36.1 MB, less than 55.24% of JavaScript online submissions for Find the Duplicate Number.

/**
 * @param {number[]} nums
 * @return {number}
 */
var findDuplicate = function (nums) {
  let slow = nums[0];
  let fast = nums[slow];
  while (slow !== fast) {
    slow = nums[slow];
    fast = nums[nums[fast]];
  }

  slow = 0;
  while (slow != fast) {
    slow = nums[slow];
    fast = nums[fast];
  }

  return slow;
};

test cases

test("test1", () => {
  expect(findDuplicate([1, 3, 4, 2, 2])).toEqual(2);
});

test("test2", () => {
  expect(findDuplicate([3, 1, 3, 4, 2])).toEqual(3);
});