剑指offer-开启美（刷）好（题）生活：第二题，不修改数组找出重复的数字

## **本文结构** --- ### **1. 题库链接** ### **2. 题目名称 ** ### **3. 题目描述** ### **4. 解题思路** ### **5. 解法代码** ### **6. 解法分析** ### **7. 疑问困惑** --- ### 1. 题库链接 https://www.acwing.com/problem/，搜索“剑指offer”。 --- ### 2. 题目名称 不修改数组找出重复的数字。 --- ### 3. 题目描述 给定一个长度为 n+1 的数组nums，数组中所有的数均在 1∼n 的范围内，其中 n≥1。请找出数组中任意一个重复的数，但不能修改输入的数组。 **样例：** 给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。返回 2 或 3。 **思考题：**如果只能使用 O(1)，的额外空间，该怎么做呢？ --- ### 4. 解题思路 结合思考题中的内容，只能使用O(1)的空间复杂度。那么我目前想到的就是时间换空间的做法。利用两层循环，外层循环得到一个数字，内层循环用这个数字和剩下的数字作比较。如果相同，则说明重复；反之，则没有重复。 --- ### 5. 解法代码 ```go func duplicateInArray(nums []int) int { for valueIndex, value := range nums { for _, testValue := range nums[valueIndex + 1:] { if value == testValue { return value } } } return -1 } ``` --- ### 6、解法分析 对于算法复杂度分析，一直不在行。这里尝试分析一波，请大牛指点一下。 外层循环的时间复杂度为：O(n)。 内层循环时间复杂度为：O(n-1)。 所以，整体算法时间复杂度为：O(n^2)。 因为没有使用额外的空间，所以空间复杂度为：O(1)。 --- ### 7、疑问困惑 1、解法分析中关于时间复杂度和空间复杂度的困惑，请大牛帮忙指点一下，我分析的对不对。 2、此题目还有没有更好的解决方法。