难度: Easy
给你一个整数数组 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
提示：
1 <= nums.length <= 105-109 <= nums[i] <= 1090 <= k <= 105运行时间: 40 ms
内存: 30.3 MB
class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
a = {}
if len(nums) ==len(set(nums)):
return False
for idx,num in enumerate(nums):
if num in a and idx-a[num] <=k:
return True
a[num] = idx
return False
题解的思路是使用哈希表来存储每个元素最后一次出现的下标。遍历数组，对于当前元素，如果它在哈希表中出现过，并且当前下标与哈希表中存储的下标之差小于等于 k，则说明存在重复元素，返回 True。否则，将当前元素和下标存入哈希表中。如果遍历完整个数组都没有找到满足条件的重复元素，则返回 False。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
# 使用哈希表存储元素最后一次出现的下标
a = {}
# 判断数组中是否存在重复元素
if len(nums) == len(set(nums)):
return False
# 遍历数组
for idx, num in enumerate(nums):
# 如果当前元素在哈希表中出现过，并且下标之差小于等于 k
if num in a and idx - a[num] <= k:
return True
# 将当前元素和下标存入哈希表中
a[num] = idx
# 如果遍历完整个数组都没有找到满足条件的重复元素，返回 False
return False
这一步是为了快速检测数组中是否存在任何重复元素。如果数组长度与去重后的集合长度相等，说明数组中所有元素都是唯一的，因此不可能存在两个相同的元素其下标之差小于或等于k。这一步虽然增加了一次完整数组的遍历，但可以在某些情况下提早结束程序，避免不必要的后续处理，特别是在大数据集中可能带来性能优势。然而，这并非必须步骤，因为主要的逻辑仍需遍历数组来检查具体的下标差条件。
在这个问题的上下文中，我们只关心元素的最近一次出现，因为我们需要的是计算当前下标与最近一次出现下标的差值。如果这个差值小于等于k，则满足题目条件，立即返回True。更新哈希表中存储的下标为最新下标，是因为这个新的下标在后续的遍历中可能会有更近的差值满足条件。之前的下标信息不再需要，因为我们只关注最近的差值是否满足条件。
如果在哈希表中找到了当前元素，但其存储的下标与当前下标的差大于k，我们仍会更新这个元素在哈希表中的下标为当前下标。这样做确保了每个元素在哈希表中的下标始终是其最后一次出现的下标。这个更新是必要的，因为它可能影响后续其他元素检查的结果，确保每次比较都是基于最近的下标信息，从而正确判断是否存在符合条件的重复元素。
当k的值非常大时，接近数组长度n，这种方法在某些情况下可能会导致性能问题。尽管最坏情况下的时间复杂度仍为O(n)，因为每个元素仍然只是简单地查找并更新哈希表，但是当k非常大时，几乎每个元素都可能在哈希表中找到匹配且其下标差小于等于k，这可以导致在遍历过程中频繁的返回True，特别是在重复元素较多的数组中。此外，存储大量元素的哈希表可能需要更多的内存空间，且在哈希表中查找和更新元素的操作虽然平均是O(1)，在极端情况下可能会接近O(n)，尤其是在哈希冲突较多的情况下。