如何不修改原数组，高效找出其中的重复数字？

本文共计993个文字，预计阅读时间需要4分钟。

数组中重复的数字，在上一次博客中提到了剑指Offer面试题3：数组中重复的数字。实际上，发现这类题目的关键就是一边遍历数组一边检查条件是否满足的元素。然后，我们在博客中用最复杂的方式学习了这类题目的解法。

数组中重复的数字

在上一篇博客中剑指Offer之面试题3: 数组中重复的数字中，其实能发现这类题目的关键就是一边遍历数组一边查满足条件的元素。

然后我们在博客​用最复杂的方式学会数组（Python实现动态数组）​这篇博客中介绍了数组这一结构的本质，并自己动手实现了一个动态数组。

今天我们介绍一下另一道来自《剑指Offer》的关于数组的面试题——不修改数组找出重复的数字。

不修改数组找出重复的数字

题目二：不修改数组找出重复的数字

给定一个长度为 n+1 的数组里的所有数字都在 0∼n 的范围内，所以数组中至少有一个数字是重复的。

请找出数组中任意一个重复的数字，但不能修改输入的数组。

样例：

给定长度为8的数组 nums = [2， 3， 5， 4，3， 2， 6，7]

那么输出重复的数字2或者3

思路

首先我们得关注到，题目要求是：不修改数组，然后还是 ​​ 返回任意一个重复的数字​​ 。