题目

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

示例 1:

输入: [1, 3, 4, 2, 2]
输出: 2

示例 2:

输入: [3, 1, 3, 4, 2]
输出: 3

说明：

• 数组中只有一个重复的数字，但它可能不止重复出现一次。

方案一（hash）

func findDuplicate(nums []int) int {
    var m = map[int]bool{}
    var res int
    for _, num := range nums {
        if _, ok := m[num]; ok {
            res = num
            break
        }
        m[num] = true
    }

    return res
}

• 时间复杂度
• 空间复杂度

空间复杂度参考：

https://leetcode-cn.com/problems/find-the-duplicate-number/solution/xun-zhao-zhong-fu-shu-by-leetcode/

原文

https://leetcode-cn.com/explore/learn/card/binary-search/215/more-practices-ii/858/