LeetCode 存在重复元素 II题解

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。

掌握哈希表的使用方法，对于解决类似的问题非常重要。