本文共 605 字，大约阅读时间需要 2 分钟。

数组中重复数字的求解问题是LeetCode中的经典问题之一。本文将详细探讨两种解决方案，并分析其优劣势。

题目描述

在一个长度为n的数组中，所有数字都在0到n-1的范围内。某些数字重复，但不知道重复次数。目标是找出数组中任意一个重复的数字。

示例

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

输出：2或3

方法一：使用哈希集合

这种方法使用哈希集合来跟踪已处理过的数字。遍历数组时，检查当前数字是否已存在于集合中：

• 如果已存在，说明重复，立即返回该数字。
• 如果不存在，将其添加到集合中。

这种方法的时间复杂度为O(n)，空间复杂度为O(n)（用于存储所有数字）。

方法二：利用数组本身

这种方法将数组本身用于哈希表的作用，并执行以下步骤：

• 遍历数组，对于每个数字i，检查nums[i]是否等于i。
• 如果不等于，则检查nums[i]是否等于nums[nums[i]]。如果相等，则返回该数字。
• 否则，交换nums[i]和nums[nums[i]]的位置，继续检查。

这种方法的时间复杂度为O(n)，空间复杂度为O(1)，节省了额外空间，但代码较为复杂。

综合分析

两种方法均能解决问题，适用于不同场景。哈希集合方法简单易懂，尤其适用于小数据量或需频繁更新集合的操作。而利用数组本身的方法更节省空间，适合处理大数据量，但代码复杂度较高。

实现时应根据具体需求选择合适的解决方案，确保在时间复杂度上的最佳平衡。

转载地址：http://tnqqz.baihongyu.com/