## **本文结构**
---
### **1. 题库链接**
### **2. 题目名称 **
### **3. 题目描述**
### **4. 解题思路**
### **5. 解法代码**
### **6. 解法分析**
### **7. 疑问困惑**
---
### 1. 题库链接
https://www.acwing.com/problem/，搜索“剑指offer”。
---
### 2. 题目名称
找出数组中重复的数字。
---
### 3. 题目描述
给定一个长度为 n 的整数数组 nums，数组中所有的数字都在 0∼n−1的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
**注意：如果某些数字不在 0∼n−1的范围内，或数组中不包含重复数字，则返回 -1。**
**样例：**给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。返回 2 或 3。
---
### 4. 解题思路
利用map，将数组nums中的元素值作为key，此元素出现的次数作为value，构造一个map。遍历数组nums，判断map[key]是否存在。如果存在，则将此key出现次数加1；反之，将此key出现次数置为1。
---
### 5. 解法代码
```go
func duplicateInArray(nums []int) int {
var duplicateMap map[int]int
var arrLen = len(nums)
duplicateMap = make(map[int]int, arrLen)
for _, value := range nums {
if value < 0 || value > arrLen - 1{
return -1
}
if v, ok := duplicateMap[value]; ok {
duplicateMap[value] = v + 1
} else {
duplicateMap[value] = 1
}
}
for k, v := range duplicateMap {
if v > 1 {
return k
}
}
return -1
}
```
---
### 6、解法分析
对于算法复杂度分析，一直不在行。这里尝试分析一波，请大牛指点一下。
```go
for _, value := range nums {
if value < 0 || value > arrLen - 1{
return -1
}
if v, ok := duplicateMap[value]; ok {
duplicateMap[value] = v + 1
} else {
duplicateMap[value] = 1
}
}
```
这个循环的时间复杂度应该是O(n)。
```go
for k, v := range duplicateMap {
if v > 1 {
return k
}
}
```
这个循环的时间复杂度应该最坏情况下是：O(n)，最好情况下是：O(1)。
所以整个算法的时间复杂度是：O(n)。
不知道这样分析对不对。
算法的空间复杂度是：O(n)。因为需要分配一个大小为n的map作为额外空间使用。
---
### 7、疑问困惑
1、解法分析中关于时间复杂度和空间复杂度的困惑，请大牛帮忙指点一下，我分析的对不对。
2、此题目还有没有更好的解决方法。
有疑问加站长微信联系（非本文作者））
