# 287. Find the Duplicate Number

## 題目敘述

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.

Example 1:

``````Input: nums = [1,3,4,2,2]
Output: 2
``````

Example 2:

``````Input: nums = [3,1,3,4,2]
Output: 3
``````

Constraints:

• `1 <= n <= 105`
• `nums.length == n + 1`
• `1 <= nums[i] <= n`
• All the integers in `nums` appear only once except for precisely one integer which appears two or more times.

• How can we prove that at least one duplicate number must exist in `nums`?
• Can you solve the problem in linear runtime complexity?

## 解法解析

### 解法範例

#### Go

``````func findDuplicate(nums []int) int {
tortoise := nums[0]
hare := nums[0]
for {
tortoise = nums[tortoise]
hare = nums[nums[hare]]
if tortoise == hare {
break
}
}

tortoise = nums[0]
for tortoise != hare {
tortoise = nums[tortoise]
hare = nums[hare]
}
return hare
}
``````

#### JavaScript

``````/**
* @param {number[]} nums
* @return {number}
*/
var findDuplicate = function (nums) {
const seen = new Set();
for (const num of nums) {
if (seen.has(num)) {
return num;
}
}
};
``````

#### Kotlin

``````class Solution {
fun findDuplicate(nums: IntArray): Int {
val seen: MutableSet<Int> = mutableSetOf()
for (num in nums) {
if (seen.contains(num)) {
return num
}
}
return -1
}
}
``````

#### PHP

``````class Solution
{

/**
* @param Integer[] \$nums
* @return Integer
*/
function findDuplicate(\$nums)
{
\$tortoise = \$hare = \$nums[0];
while (true) {
\$tortoise = \$nums[\$tortoise];
\$hare = \$nums[\$nums[\$hare]];
if (\$tortoise == \$hare) {
break;
}
}

\$tortoise = \$nums[0];
while (\$tortoise != \$hare) {
\$tortoise = \$nums[\$tortoise];
\$hare = \$nums[\$hare];
}
return \$hare;
}
}
``````

#### Python

``````class Solution:
def findDuplicate(self, nums: List[int]) -> int:
seen = set()
for num in nums:
if num in seen:
return num
``````

#### Rust

``````impl Solution {
pub fn find_duplicate(nums: Vec<i32>) -> i32 {
let mut tortoise = nums[0];
let mut hare = nums[nums[0] as usize];
while tortoise != hare {
tortoise = nums[tortoise as usize];
hare = nums[nums[hare as usize] as usize];
}

tortoise = 0;
while tortoise != hare {
tortoise = nums[tortoise as usize];
hare = nums[hare as usize];
}
tortoise
}
}
``````

#### Swift

``````class Solution {
func findDuplicate(_ nums: [Int]) -> Int {
var duplicate = 0
var seen = Set<Int>()
for num in nums {
if seen.update(with: num) != nil {
duplicate = num
break
}
}
return duplicate
}
}
``````