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。掌握哈希表的使用方法对于解决类似的问题非常重要。