用哈希表求解力扣第217题 存在重复元素

前言

记录一下刷题历程 力扣第217题存在重复元素

两数之和

原题目：给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。
示例 1：

输入：nums = [1,2,3,1]
输出：true
示例 2：

输入：nums = [1,2,3,4]
输出：false
示例 3：

输入：nums = [1,1,1,3,3,4,3,2,4,2]
输出：true

分析

可以使用一个哈希表用来存储数组中的元素和出现情况。遍历数组检查当前数组元素是否意境存入哈希表中，如果存在则找到了重复元素，如果没有则将该元素存入哈希表中

代码如下：

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        // 创建一个哈希表（unordered_map），用于存储数组中的元素及其出现情况
        unordered_map<int, int> u_map;
        
        // 遍历数组中的每一个元素
        for (int i = 0; i < nums.size(); i++) {
            // 检查当前元素是否已经存在于哈希表中
            if (u_map.count(nums[i])) {
                // 如果存在，说明找到了重复的元素
                return true;
            }
            
            // 如果不存在，将当前元素和其值（这里值为1，表示出现过）加入哈希表
            u_map[nums[i]] = 1;
        }
        
        // 如果遍历完数组没有找到重复的元素，返回 false
        return false;
    }
};

解释注释

1.unordered_map<int, int> u_map;

创建一个 unordered_map（哈希表）u_map，用于存储数组中每个元素及其出现情况。键是元素的值，值是一个整数（在这里值是 1，表示该元素出现过）。

2.if (u_map.count(nums[i]))

使用 count 函数检查哈希表中是否存在当前元素 nums[i]。count 函数返回元素在哈希表中出现的次数，如果返回值大于 0，说明元素已经存在。

3.u_map[nums[i]] = 1;

如果当前元素不在哈希表中，将其加入哈希表，并将对应的值设置为 1。这表示该元素已经出现过一次。

时间复杂度

这个方法的时间复杂度是 O(n)，其中 n 是数组 nums 的大小，因为每个元素被遍历一次。哈希表的插入和查找操作都是常数时间复杂度，因此整体时间复杂度是 O(n)。