html5技术可以制作网站吗,wordpress时尚英文站,自己动手做导航网站,网站做效果联系方式219. 存在重复元素 II 解题思路
问题描述
给定一个整数数组 nums 和一个整数 k#xff0c;要求判断数组中是否存在两个 不同的索引 i 和 j#xff0c;使得#xff1a;
nums[i] nums[j]且满足 abs(i - j) k
如果满足上述条件#xff0c;返回 true#xff0c;否则…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):遍历数组 numsi 是索引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) 的性能瓶颈。
