# LeetCode Solution, Medium, 287. Find the Duplicate Number

# [287. Find the Duplicate Number](https://leetcode.com/problems/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.

**Follow up:**

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

### 題目翻譯

給定一個整數陣列 `nums`，其中的元素只有一個整數值是會重複的(且可以重複一次以上)。請在沒有修改 `nums` 的情況下解出這問題。其中 `nums` 的元素的範圍只會在 `[1, n]` 中，而`n` 是 `nums` 的長度。

## 解法解析

這題有許多的解法，雖然官方給了相當多的解法，有提到說前四種解法並不符合題目的需求，就是違反了 **不修改 `nums`** 的原則。像是 Sort 和 Negative Marking 的解法，但還是提出來是因為在面試時是個快速的解題方式。

看過各種程式語言的解法，大部分會採用以下幾種：Set, Hash Map, Floyd's Tortoise and Hare。以下的解法範例中 Go、PHP、Rust 就是使用了 Floyd's Tortoise and Hare 的解法，其他語言則是使用了 Set 的解法。因為 Floyd's Tortoise and Hare 的解法是在符合題目條件下，其時間複雜度最佳的解法。

一開始不是很懂為什麼可以用 Floyd's Tortoise and Hare 的解法，為什麼可以變成一個循環？後來看到條件是 `[1, n]` 才搞懂。因為這個條件，所以每個元素可以相對應彼此的 index，而不會超出 index 範圍。`[1, 3, 2, 4, 5, 2]` => `n = 6`。而重複的元素就會是循環的起始點，所以剛好就符合 Floyd's Tortoise and Hare 的情境

### 解法範例

#### Go

```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

```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;
        }
        seen.add(num);
    }
};
```

#### Kotlin

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

#### PHP

```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

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

#### Rust

```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

```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
    }
}
```