Find Duplicate Number

Write a function `find_duplicate(nums)` that takes a list of integers `nums`. The list contains `n + 1` integers where `n = len(nums) - 1`. Each integer is between `1` and `n` inclusive. Because there are `n + 1` numbers and only `n` possible values, at least one number appears more than once. Your function should return the integer that appears more than once. If multiple numbers appear more than once, return the first one encountered when scanning the list from left to right that has already appeared earlier in the list. For example, in `[2, 1, 3, 1]`, the duplicate is `1` because it appears twice. In `[3, 1, 3, 4, 2]`, the duplicate is `3` because it appears twice and is the only duplicate. In `[1, 2, 2, 3, 3]`, the duplicate is `2` because scanning left to right, `2` is the first number that repeats. You may assume the input is always valid: it will always have at least one duplicate, and all numbers are in the range `1` to `len(nums)-1` inclusive. Constraints: - `1 <= len(nums) <= 10^6` - The function should run in O(n) time and O(n) extra space. Do not modify the input list.

>>> find_duplicate([2, 1, 3, 1])
1
>>> find_duplicate([3, 1, 3, 4, 2])
3
>>> find_duplicate([1, 2, 2, 3, 3])
2
>>> find_duplicate([1, 1])
1