# 剑指 Offer 03. 数组中重复的数字

大家好,我是吴师兄。

今天继续来学习《剑指Offer》系列的一道经典题目,依旧给出了非常详细的题解和精美的配图与动画。

# 一、题目描述

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。

请找出数组中任意一个重复的数字。

示例 1:

输入:
[2, 3, 1, 0, 2, 5, 3]
输出:2 或 3 

# 二、题目解析

注意题目描述:一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的 范围内,这个 范围 恰好与数组的下标可以一一对应。

所以我们可以执行某种操作,使索引与值一一对应,即索引 0 的值为 0,索引 1 的值为 1。而一旦某个索引的值不只一个,则找到了重复的数字,也即发生了 哈希冲突

为了帮助你更好的理解整个过程,我特意做了一组动画,点开可以查看

# 三、参考代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 剑指 Offer 03. 数组中重复的数字:https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/
class Solution {
    public int findRepeatNumber(int[] nums) {

        // HashSet 的特点是不会存储重复元素
        // 所以可以利用 HashSet 来查找出重复的元素
        Set<Integer> dic = new HashSet<>();

        // 遍历数组,设置此时遍历的元素为 num
        for(int num : nums) {
            
            // 如果发现 dic 中已经存储了 num
            // 那么说明找到了重复的那个元素
            if(dic.contains(num)) {
                // 把 num 这个结果进行返回
                return num;

            // 否则的话,说明 dic 中还没有存储 num
            }else{
                // 把 num 添加到 dic 中
                dic.add(num);
            }
           
        }

        // 由于 nums 中所有的数字都在 0 ~ n-1 的范围内
        // 所以负数,比如 -1 必然不在 nums 这个范围内
        // 如果没有找到重复的数字,那么返回 -1
        return -1;
    }
}