哈希表_存在重复元素|、存在重复元素||_C++

---

1. 存在重复元素|

---

leetcode链接：https://leetcode.cn/problems/contains-duplicate/description/

1. 题目描述

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

• 示例 1：

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

• 解释：元素 1 在下标 0 和 3 出现。

2. 算法原理

• 遍历数组，并将元素加入hash表中，如果出现某一个元素数量大于1的情况，则说明出现了重复元素。

3. 代码实现

class Solution {
public:bool containsDuplicate(vector<int>& nums) {unordered_map<int, int> hash;int n = nums.size();for (int i = 0; i < n; i++){hash[nums[i]]++;if (hash[nums[i]] > 1) return true;}return false;}
};

---

2. 存在重复元素||

---

leetcode链接：https://leetcode.cn/problems/contains-duplicate-ii/description/

1. 题目描述

• 给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

• 示例 1：

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

• 示例 2：

输入：nums = [1,0,1,1], k = 1
输出：true

• 示例 3：

输入：nums = [1,2,3,1,2,3], k = 2
输出：false

2. 算法原理

• 还是从前往后遍历，同时将元素加入hash。由于本题需要判断下标之间的差是否满足条件，所以hash的定义为<nums[i], i>，即值存的是下标。

3. 代码实现

class Solution {
public:bool containsNearbyDuplicate(vector<int>& nums, int k) {unordered_map<int, int> hash;for (int i = 0; i < nums.size(); i++){if (hash.count(nums[i])){if (abs(hash[nums[i]] - i) <= k)return true;elsehash[nums[i]] = i;}elsehash[nums[i]] = i;}return false;}
};

---