搭建网站公司哪家好小辉seo
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^90 <= 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 Truelast[x] = ireturn 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。
边界情况
- 数组长度为 1：如果数组只有一个元素，显然不可能有两个不同的索引满足条件，应该直接返回
False。 - k = 0：如果
k为 0，表示要求两个相同的数字索引是完全相同的，因此当nums中有重复元素时，返回True，否则返回False。
总结
这道题考察了如何使用哈希表进行高效查找。通过记录每个元素上次出现的索引，并在遍历过程中进行条件判断，我们能够在 O(n) 的时间复杂度内完成任务，避免了暴力解法中 O(n^2) 的性能瓶颈。