四川建设安全监督管理局网站网站运营推广公司

代码训练(17)LeetCode之存在重复元素

Author: Once Day Date: 2024年5月7日

漫漫长路，才刚刚开始…

全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客

参考文章:

• 219. 存在重复元素 II - 力扣（LeetCode）
• 力扣 (LeetCode) 全球极客挚爱的技术成长平台

1. 原题

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

• 1 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9
• 0 <= k <= 10^5

例如对于nums = [1,2,3,1,2,3], k = 2，不存在间隔两个以内的相等值，因此返回False。

2. 分析

该题目要求我们判断一个给定的整数数组 nums 中是否存在两个不同的索引 i 和 j，使得 nums[i] == nums[j] 且两个索引的差的绝对值不大于 k。如果存在这样的一对索引，则返回 true，否则返回 false。

要解决这个问题，可以采用哈希表记录法：

• 创建一个哈希表来存储数组值和其对应的最新索引。
• 遍历数组，对于每个元素，检查哈希表中是否已经存在该元素：
  • 如果存在，则比较当前索引与哈希表中存储的索引的差的绝对值是否不大于 k。
  • 如果满足条件，则直接返回 true。
  • 如果不满足条件，或者元素不存在于哈希表中，则更新哈希表，将该元素的索引设置为当前索引。
• 如果遍历完数组后没有找到符合条件的元素对，则返回 false。

分析步骤：

1. 初始化一个空的哈希表 map。
2. 遍历数组 nums，对于每个元素 nums[i]：
   • 检查 nums[i] 是否已存在于 map 中。
   • 如果存在，计算当前索引 i 和 map[nums[i]] 的差的绝对值。
   • 如果这个差值小于等于 k，返回 true。
   • 否则，更新 map[nums[i]] 为当前索引 i。
3. 遍历结束后，如果没有找到符合条件的索引对，返回 false。

举例分析，以 nums = [1,2,3,1], k = 3 为例：

• 初始化 map = {}。
• 遍历 nums：
  • i = 0，nums[i] = 1，map 更新为 {1: 0}。
  • i = 1，nums[i] = 2，map 更新为 {1: 0, 2: 1}。
  • i = 2，nums[i] = 3，map 更新为 {1: 0, 2: 1, 3: 2}。
  • i = 3，nums[i] = 1，发现 1 已存在，且 abs(3 - 0) = 3，满足条件，返回 true。

性能优化关键点：

• 哈希表的使用：通过使用哈希表来快速查找和更新元素索引，复杂度为 O(1)。
• 一次遍历：只需要遍历一次数组，时间复杂度为 O(n)，其中 n 是数组的长度。

3. 代码实现

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>bool containsNearbyDuplicate(int* nums, int numsSize, int k) {int* map = (int*)calloc(200001, sizeof(int));for (int i = 0; i < numsSize; i++) {int num = nums[i] + 100000;  // Offset to handle negative indicesif (map[num] != 0 && i - (map[num] - 1) <= k) {free(map);return true;}map[num] = i + 1;  // Store index + 1 to distinguish from initial zero}free(map);return false;
}int main() {int nums[] = {1, 2, 3, 1};int k = 3;int numsSize = sizeof(nums) / sizeof(nums[0]);bool result = containsNearbyDuplicate(nums, numsSize, k);printf("Result: %s\n", result ? "true" : "false");return 0;
}

这段代码实现了一个函数 containsNearbyDuplicate，用于检查给定的整数数组 nums 中是否存在两个相同的元素，它们的下标之差的绝对值小于等于 k。

代码使用了哈希表的思想来优化查找效率。哈希表的大小为 HashSize，定义为 0x1fff + 1，即 8192。哈希表使用链表法解决哈希冲突，每个哈希桶都是一个链表的头节点。

函数 hash_reset 用于重置哈希表，释放所有节点的内存。

函数 containsNearbyDuplicate 的主要步骤如下：

1. 重置哈希表。
2. 遍历数组 nums，对于每个元素：
   • 计算哈希索引 nums[i] & 0x1fff，即将元素的低 13 位作为哈希索引。
   • 在对应的哈希桶中查找是否存在相同的元素，且下标之差的绝对值小于等于 k，如果找到则返回 true。
   • 如果没有找到，则创建一个新的节点，存储当前元素的值和下标，插入到哈希桶的链表中。
3. 如果遍历完整个数组都没有找到符合条件的元素对，则返回 false。

运行结果如下所示(仅供参考):

这段代码写得很暴力，优化空间很大:

1. 哈希表的大小 HashSize 可以根据实际情况进行调整，选择一个合适的大小以平衡内存使用和哈希冲突的概率。
2. 可以考虑使用更高效的哈希函数，例如使用素数取模或者其他哈希算法，以减少哈希冲突的概率。
3. 在插入新节点时，可以先判断链表的长度是否超过了一定的阈值，如果超过了，可以考虑将链表转换为其他数据结构，如红黑树，以提高查找效率。
4. 可以考虑在插入新节点时，如果链表长度超过了 k，则可以直接删除链表头部的节点，因为它们的下标之差肯定大于 k，不会影响结果。

4. 总结

本题主要考查对数组遍历和哈希表的应用能力。通过使用哈希表存储元素的最新索引，我们能够有效检查是否有符合条件的索引对。这种方法利用了哈希表快速查找和插入的特性，使得时间复杂度控制在 O(n) 内，适合处理大规模数据。