1. 问题回顾与约束

• 数组长度为 $n+1$，元素都在 $[1,n]$ 的范围内。
• 因「鸽巢原理」，必存在至少一个值出现两次或以上。
• 要求：
  1. 不能 修改输入数组；
  2. 只允许 $O(1)$ 额外空间；
  3. 时间复杂度 $O(n)$。

常见但不满足约束的方法有：

Leetcode 100.寻找重复数-原题链接

题目描述

给定一个包含 $n + 1$ 个整数的数组 nums，其数字都在 $[1, n]$ 范围内（包括 $1$ 和 $n$），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数，返回 这个重复的数。

你的解决方案必须 不修改 数组 nums，且只用常量级 $O(1)$ 的额外空间。

输入描述

• 第一行输入一个整数 n（$1 \leq n \leq 10^5$），表示 nums 的长度为 $n + 1$。
• 第二行输入 n + 1 个整数，表示数组 nums。

输出描述

输出 nums 中唯一的重复整数。

输入示例

4
1 3 4 2 2

输出示例

2

提示

• nums 的长度始终为 n + 1。
• nums 中的所有数字都在 [1, n] 范围内。
• nums 中 只有一个整数出现两次或多次，其余整数均只出现一次。