## 1. 问题背景与核心挑战 在算法面试和日常编程中，数组处理是永恒的主题。LeetCode第287题"寻找重复数"看似简单，却暗藏玄机。题目给定一个包含n+1个整数的数组nums，其中每个整数都在1到n之间（包括1和n），要求找出数组中唯一的重复数字。这个问题的经典解法往往让人眼前一亮——它完美融合了数组特性、数学思维和算法优化。 我第一次遇到这个问题时，下意识想用哈希表解决，直到发现题目要求必须满足O(1)空间复杂度时才意识到没那么简单。这道题真正考验的是对数组本身特性的理解，以及如何将数组索引与值的关系转化为数学问题。下面我将拆解三种主流解法，并分享实际编码中的优化技巧。 ## 2. 解法一：暴力搜索与哈希表（非最优解） ### 2.1 基础实现思路 最直观的解法是双重循环暴力搜索： ```java for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { if (nums[i] == nums[j]) { return nums[i]; } } }

时间复杂度O(n²)，空间复杂度O(1)，但显然无法满足大规模数据需求。

2.2 哈希表优化版

使用HashSet可以降低时间复杂度：

Set<Integer> seen = new HashSet<>(); for (int num : nums) { if (seen.contains(num)) { return num; } seen.add(num); }

时间复杂度O(n)，但空间复杂度也是O(n)，仍不符合题目进阶要求。

注意：虽然这两种解法不符合题目最优要求，但在实际工程中，当空间复杂度不是首要考虑因素时，哈希表解法仍然是可靠选择。

3. 解法二：排序预处理法

3.1 实现步骤

1. 先对数组排序（Arrays.sort）
2. 遍历比较相邻元素

Arrays.sort(nums); for (int i = 1; i < nums.length; i++) { if (nums[i] == nums[i-1]) { return nums[i]; } }

3.2 复杂度分析

• 时间复杂度：O(n log n)（主要来自排序）
• 空间复杂度：O(1)（原地排序）或O(n)（非原地排序）

实操心得：Java的Arrays.sort()对原始类型使用双轴快排，对象类型使用TimSort。虽然时间复杂度不理想，但在实际面试中可以先提出这种解法作为过渡。

4. 解法三：弗洛伊德判圈算法（最优解）

4.1 算法原理

这个解法将数组视为链表，利用快慢指针寻找环的入口：

1. 将数组值看作链表next指针（nums[i]表示节点i指向的下一个节点）
2. 由于存在重复数字，必然存在环
3. 通过快慢指针找到环入口即为重复数字

4.2 数学证明

设环长为L，从起点到环入口距离为F，相遇点到环入口距离为a：

• 慢指针路程：F + a
• 快指针路程：2(F + a) = F + a + kL
• 得出F = (k-1)L + (L - a)

这意味着从起点和相遇点同时出发的两个指针，必在环入口相遇。

4.3 Java实现

int slow = nums[0]; int fast = nums[0]; do { slow = nums[slow]; fast = nums[nums[fast]]; } while (slow != fast); slow = nums[0]; while (slow != fast) { slow = nums[slow]; fast = nums[fast]; } return slow;

4.4 复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)

5. 边界条件与异常处理

5.1 输入校验

if (nums == null || nums.length < 2) { throw new IllegalArgumentException("Invalid input"); }

5.2 数值范围验证

for (int num : nums) { if (num < 1 || num > nums.length - 1) { throw new IllegalArgumentException("Value out of range"); } }

6. 性能测试对比

使用JMH进行基准测试（n=10000）：

7. 实际应用场景

1. 数据库索引检查：检测是否存在重复索引键
2. 网络路由检测：发现路由表中的循环路径
3. 生物信息学：DNA序列重复片段识别
4. 版本控制系统：检测提交历史中的循环依赖

8. 算法变种与扩展

8.1 多个重复数的情况

如果允许存在多个重复数，可以：

1. 使用BitSet记录出现过的数字
2. 遍历时检查并记录重复数

8.2 不修改数组的解法

当不允许修改原数组时：

1. 使用二分查找统计区间计数
2. 时间复杂度O(n log n)，空间O(1)

9. 常见面试问题与回答技巧

Q：为什么这个算法能保证找到重复数？ A：可以将数组视为链表，重复数必然导致环，而环的入口就是重复数字。通过快慢指针可以定位环入口。

Q：如果数组中有多个重复数怎么办？ A：原算法只能找到一个。如果需要找全部，可以考虑使用辅助数据结构如HashMap，但会牺牲空间复杂度。

10. 编码风格建议

1. 使用final变量增强可读性：

final int n = nums.length - 1;

2. 添加防御性编程：

Objects.requireNonNull(nums);

3. 方法注释应包含复杂度说明：

/** * Finds the duplicate number using Floyd's algorithm * Time: O(n), Space: O(1) */

11. 单元测试用例设计

@Test public void testFindDuplicate() { // 基础用例 assertEquals(2, findDuplicate(new int[]{1,3,4,2,2})); // 边界用例 assertEquals(1, findDuplicate(new int[]{1,1})); // 大数用例 int[] largeArray = new int[10001]; Arrays.fill(largeArray, 42); assertEquals(42, findDuplicate(largeArray)); // 异常测试 assertThrows(IllegalArgumentException.class, () -> findDuplicate(new int[]{1})); }

12. 算法可视化技巧

在面试中画图说明：

1. 绘制数组索引与值的指向关系
2. 标记快慢指针的移动路径
3. 标出环的入口位置

示例：

索引: 0 -> 1 -> 3 -> 2 ^------|

13. 性能优化实战

当n极大时（>1e6）：

1. 考虑使用位运算替代弗洛伊德算法
2. 分段处理大数据（外存算法）
3. 并行化处理（MapReduce）

14. 不同语言实现对比

Python实现更简洁但性能较差：

def findDuplicate(nums): slow = fast = nums[0] while True: slow = nums[slow] fast = nums[nums[fast]] if slow == fast: break slow = nums[0] while slow != fast: slow = nums[slow] fast = nums[fast] return slow

15. 历史背景与衍生问题

该算法衍生自：

1. 图论中的环检测
2. 链表相交问题
3. 数论中的鸽巢原理

类似问题：

• LeetCode 142 环形链表II
• LeetCode 268 缺失数字