LeetCode 存在重复元素 II题解
题目描述
给定一个整数数组和一个整数k，判断数组中是否存在两个不同的索引i和j，使得nums[i] = nums[j]，并且abs(i - j) <= k。
示例：
输入：nums = [1,2,3,1],k = 3
输出：true
输入：nums = [1,0,1,1],k = 1
输出：true
解题思路
方法：哈希表
思路：
- 使用哈希表来解决这个问题。
- 遍历数组，对于每个元素，检查它是否已经在哈希表中。
- 如果在哈希表中存在，计算当前索引与哈希表中存储的索引之间的差值。
- 如果差值小于等于 k，返回 True。
- 如果不在哈希表中或差值大于 k，将当前元素和其索引存入哈希表。
- 如果遍历完成，返回 False。
复杂度分析：
- 时间复杂度：O(n)，其中 n 是数组的长度。每个元素最多被访问一次。
- 空间复杂度：O(n)，需要额外的空间来存储哈希表。
代码实现
方法：哈希表
# 存在重复元素 II（哈希表） def contains_nearby_duplicate(nums, k): hash_map = {} for i, num in enumerate(nums): if num in hash_map and i - hash_map[num] <= k: return True hash_map[num] = i return False # 测试 def test_contains_nearby_duplicate(): nums = [1, 2, 3, 1] k = 3 print(contains_nearby_duplicate(nums, k)) # 输出：True nums = [1, 0, 1, 1] k = 1 print(contains_nearby_duplicate(nums, k)) # 输出：True if __name__ == "__main__": test_contains_nearby_duplicate()测试用例
测试用例 1：基本情况
输入：nums = [1,2,3,1],k = 3
输出：true
测试用例 2：相邻重复元素
输入：nums = [1,0,1,1],k = 1
输出：true
总结
存在重复元素 II 是一个经典的哈希表问题，它可以通过哈希表来高效地解决。
哈希表法的核心思想是：遍历数组，检查每个元素是否已经在哈希表中存在，如果存在且索引差值小于等于 k，返回 True。
掌握哈希表的使用方法，对于解决类似的问题非常重要。
