[数据结构与算法]剑指 Offer 03.数组中重复的数字

算法：哈希表

时间复杂度：O[N]

题目链接：剑指 Offer 03.数组中重复的数字

看到这题很容易想到用到哈希表的知识

算法流程

• 创建一个hash表p，存放数组中每一个数的bool值
• 若为false将这个数bool值变为ture作为标记，反之则直接return

代码

c++代码

/*剑指 Offer 03.数组中重复的数字*/
class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        unordered_map<int,bool> p;
        for (int num:nums) {
            if (p[num]) return num;
            p[num] = 1;
        }
        return -1;
    }
};

Java代码

class Solution {
    public int findRepeatNumber(int[] nums) {
        Set<Integer> p = new HashSet<>();
        for (int num:nums) {
            if (p.contains(num)) return num;
            p.add(num);
        }
        return -1;
    }
}
//tip:contains() 函数用于查找动态数组中的数