题目内容

存在一个长度为 $n+1$ 的整数数组 nums，其中每个元素都是 $1$ 到 $n$ 之间的整数。因此，nums 中必定至少有一个整数重复出现。本题保证重复出现的整数值只有一个，其余整数均只出现一次。请找出这个重复出现的整数。

求解时不得修改数组 nums，并且额外空间复杂度必须为 $O(1)$。

约束条件：

• nums 的长度为 $n+1$，其中 $1 \le n \le 10^5$。
• 对任意下标 $i$，都有 $1 \le nums[i] \le n$。
• nums 中恰好只有一个整数会出现超过一次，其余整数均只出现一次。

输入描述

输入包含一个参数：一个整数列表 nums，表示待查找的数组。

输出描述

返回一个整数，表示 nums 中重复出现的那个整数。

样例1

输入

1
1 1

输出

1

说明

数组元素依次为 1 和 1，值范围是 $[1,1]$。整数 1 出现了 2 次，因此重复的整数是 1。

样例2

输入

5
2 5 1 1 3 4

输出

1

说明

数组元素依次为 2、5、1、1、3、4，值范围是 $[1,5]$。整数 1 出现了 2 次，2、5、3、4 各出现 1 次，因此重复的整数是 1。

从数组第一个元素 2 开始按元素值跳转，访问顺序为 2 → 1 → 5 → 4 → 3 → 1，第二次遇到 1，也对应重复整数 1。

样例3

输入

4
2 1 3 4 2

输出

2

说明

数组元素依次为 2、1、3、4、2，值范围是 $[1,4]$。整数 2 出现了 2 次，1、3、4 各出现 1 次，因此重复整数是 2。

从数组第一个元素 2 开始按元素值跳转，访问顺序为 2 → 3 → 4 → 2，第二次遇到 2，因此输出 2。