一、问题描述

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1：

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3

限制：

2 <= n <= 100000

二、我的解法一

遍历法：

func findRepeatNumber(nums []int) int {
	for i := 0; i < len(nums); i++ {
		for j := i + 1; j < len(nums); j++ {
			if nums[i] == nums[j] {
				return nums[i]
			}
		}
	}
	return 0
}

评判结果：

可见遍历法还是太慢了。需要想其他更好的解法。

三、我的解法二

1. 使用哈希表

func findRepeatNumber(nums []int) int {

	hashtable := map[int]int{}
	tag := 0
	for i, num := range nums {
		tag++
		hashtable[num] = i
		if len(hashtable) != tag {
			return num
		}
	}
	return 0
}

评判结果：

我们利用哈希表的键不能重复的特性：在给空哈希表不断填值的过程中，遇到已存在的键，不会新建键，而是将键所对应的值做更改。

所以我们用 tag 指示我们在将第几对键值对往哈希表中加。

如果遇到了重复的键（原数组的值），哈希表不会再新建一个键值对，那么哈希表的长度和 tag 的值将会出现不一致。

这时候我们返回这个重复的数字就好啦~

2. 改进 – 用空结构体省存储空间

但是，该程序的存储空间和用时还是不够低，我们进一步降低存储空间：

func findRepeatNumber(nums []int) int {
	//自定义一个空结构体数据类型 n
    type n struct{}     //空结构体不占用任何的内存空间, 一般把它当作占位符来用
	var v n             //声明一个 n 类型的变量 v
	hashtable := map[int]n{}
	tag := 0
	for _, num := range nums {
		tag++
		hashtable[num] = v 
		if len(hashtable) != tag {
			return num
		}
	}
	return 0
}