企业官网建设流程全解析

【C++算法打怪专栏】LeetCode 217. 存在重复元素（解法总结）

一、 题目链接

• LeetCode 官方网址：LeetCode 217. 存在重复元素

二、 核心思路对比

判断数组中是否存在重复元素，最经典且高效的方案是利用哈希表结构。通常有两种主流写法：

1. 方法一：哈希集合unordered_set（最优解）

   • 核心思想：因为我们只关心“某个元素有没有出现过”，不需要记录具体的次数或下标，所以使用unordered_set最为合适。
   • 执行流程：遍历数组，检查当前元素是否已经在set中：
     • 如果已存在，说明重复，直接返回true。
     • 如果不存在，将其插入set中。
     • 遍历结束若无重复，返回false。

2. 方法二：哈希映射unordered_map（计数法）

   • 核心思想：利用unordered_map记录每个元素出现的频次。
   • 执行流程：遍历数组，将当前元素的计数加 1（mp[nums[i]]++），随后检查其频次是否大于 1：
     • 如果大于 1，说明重复，直接返回true。
     • 遍历结束若频次均不大于 1，返回false。

三、 C++ 标准精简源码

方法一：unordered_set（推荐）

#include<vector>#include<unordered_set>usingnamespacestd;classSolution{public:boolcontainsDuplicate(vector<int>&nums){unordered_set<int>un;// 只需一个模板参数for(inti:nums){// 如果在集合中找到了当前元素，说明重复if(un.find(i)!=un.end()){returntrue;}un.insert(i);}returnfalse;}};

方法二：unordered_map

#include<vector>#include<unordered_map>usingnamespacestd;classSolution{public:boolcontainsDuplicate(vector<int>&nums){unordered_map<int,int>mp;// 键：数值，值：出现次数for(inti=0;i<nums.size();i++){mp[nums[i]]++;// 如果当前数字出现次数超过 1 次，说明重复if(mp[nums[i]]>1){returntrue;}}returnfalse;}};

四、 复杂度分析

• 时间复杂度：O ( N ) O(N)O(N)，其中N NN是数组的长度。我们对数组进行了一次单循环，哈希容器的查找、插入及更新操作平均时间复杂度均为O ( 1 ) O(1)O(1)。
• 空间复杂度：O ( N ) O(N)O(N)，最坏情况下（数组中无重复元素），需要将所有元素存入哈希容器中。