当前位置：首页 > article >正文

【力扣每日一题】存在重复元素 II 解题思路

article 2025/1/30 20:12:06

219. 存在重复元素 II 解题思路

问题描述

给定一个整数数组 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 <= 10^5
-10^9 <= nums[i] <= 10^9
0 <= k <= 10^5

解题思路

这道题可以通过哈希表来实现高效的查找。我们需要检查数组中是否存在两个相同的元素，其索引差值不超过 k。一个直观的做法是利用哈希表记录每个数字上次出现的位置，并与当前索引进行比较。

详细步骤：

使用一个字典 last 来存储每个数字最近一次出现的索引。
遍历 nums 数组中的每个元素，对于每个元素：
- 如果当前数字已经出现在字典中，计算当前索引与上次索引的差值。
- 如果差值小于等于 k，直接返回 True，表示满足条件。
- 如果差值大于 k，更新字典中该数字的最新索引为当前索引。
如果遍历结束后没有找到符合条件的两个元素，返回 False。

时间复杂度分析：

遍历数组的时间复杂度是 O(n)，其中 n 是数组 nums 的长度。
哈希表的插入和查找操作平均时间复杂度是 O(1)。
因此，总时间复杂度为 O(n)。

空间复杂度分析：

需要使用哈希表来存储数字和对应的索引，最坏情况下哈希表中可能存储 n 个元素，因此空间复杂度是 O(n)。

代码实现

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        last = {}
        for i, x in enumerate(nums):
            if x in last and abs(last[x] - i) <= k:
                return True
            last[x] = i
        return False

代码解释：

last = {}：初始化一个空字典，用于存储数字及其最近的索引。
for i, x in enumerate(nums):：遍历数组 nums，i 是索引，x 是当前元素。
if x in last and abs(last[x] - i) <= k:：检查当前数字 x 是否在字典 last 中，如果在，计算当前索引 i 与上次索引 last[x] 之间的差值。如果差值小于等于 k，返回 True。
last[x] = i：更新字典 last 中数字 x 的最新索引。
return False：遍历结束后如果没有满足条件的元素，返回 False。