寻找重复的数字
考点，哈希表，或者带环链表的遍历
package leetcodemid.findduplicate;
/**
* 287. 寻找重复数
* 给定一个包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。
* <p>
* 假设 nums 只有 一个重复的整数 ，找出 这个重复的数 。
* <p>
* 你设计的解决方案必须不修改数组 nums 且只用常量级 O(1) 的额外空间。
* <p>
* <p>
* <p>
* 示例 1：
* <p>
* 输入：nums = [1,3,4,2,2]
* 输出：2
* 示例 2：
* <p>
* 输入：nums = [3,1,3,4,2]
* 输出：3
* 示例 3：
* <p>
* 输入：nums = [1,1]
* 输出：1
* 示例 4：
* <p>
* 输入：nums = [1,1,2]
* 输出：1
* <p>
* <p>
* 提示：
* <p>
* 1 <= n <= 105
* nums.length == n + 1
* 1 <= nums[i] <= n
* nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次
* <p>
* <p>
* 进阶：
* <p>
* 如何证明 nums 中至少存在一个重复的数字?
* 你可以设计一个线性级时间复杂度 O(n) 的解决方案吗？
*
*
* 1. 思路1：双指针遍历是否成环
* 2. 思路2：哈希表，不过是用数组，本题用思路2
*
* @return
*/
public class FindDuplicate {
//思路2：哈希表，不过是用数组，本题用思路2
public static int findDuplicate(int[] nums) {
int[] res = new int[nums.length+1];
for (int i = 0; i < nums.length; i++) {
//4 在nums[4]中
res[nums[i]]++;
}
for (int i = 0; i < res.length; i++) {
if(res[i]>1){
return i;
}
}
return 0;
}
public static void main(String[] args) {
int[] nums = {3,1,3,4,2};
System.out.println(findDuplicate(nums));
}
}