哈希表_存在重复元素|、存在重复元素||_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;
                else
                    hash[nums[i]] = i;
            }
            else
                hash[nums[i]] = i;
        }
        return false;
    }
};

---

原文地址：https://blog.csdn.net/weixin_73870552/article/details/142745038

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！