[LeetCode] 每日一题 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
解题思路
本题是典型的哈希表应用,目标是在数组 nums
中查找是否存在两个不同索引 i
和 j
,使得 nums[i] == nums[j]
,同时满足 abs(i - j) <= k
。为了高效地完成这一查找过程,我们可以使用哈希表(HashMap
),其中键(key
)存储数组的值,值(value
)存储该值对应的最新索引
在遍历数组时,我们执行以下操作:
检查是否存在相同的值:如果
nums[i]
已经在哈希表中存在,说明之前出现过相同的值计算索引差值:如果当前索引
i
与哈希表存储的索引之差不超过k
,则直接返回true
更新索引:如果
nums[i]
之前出现过,但索引间隔大于k
,则用当前索引覆盖哈希表中的旧索引。这是一个贪心策略,确保存储的索引尽可能接近当前索引,以便未来的匹配更有可能满足条件
该方法通过一趟遍历完成检查,保证了较高的效率
代码实现
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(nums[i]) && i - map.get(nums[i]) <= k) {
return true;
}
map.put(nums[i], i);
}
return false;
}
}
复杂度分析
时间复杂度:O(n),其中
n
是数组nums
的长度。遍历数组时,每个元素最多进行一次哈希查找和一次哈希插入操作,均摊复杂度为 O(1),因此整体复杂度为 O(n)。空间复杂度:O(n),最坏情况下,数组中所有元素都不重复,则需要存储
n
个键值对。
总结
本题利用哈希表高效地解决了索引匹配问题,确保了时间复杂度为 O(n)。在解法中,我们应用了贪心思想,每次遍历时存储最新的索引,以确保后续的匹配更容易满足条件。该方法避免了暴力解法的 O(n²) 复杂度,使得处理大规模数据时更加高效。
希望这篇分享能为你带来启发!如果你有任何问题或建议,欢迎在评论区留言,与我共同交流探讨。