文章

[LeetCode] 每日一题 219. 存在重复元素 II

题目链接

https://leetcode.cn/problems/contains-duplicate-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 中查找是否存在两个不同索引 ij,使得 nums[i] == nums[j],同时满足 abs(i - j) <= k。为了高效地完成这一查找过程,我们可以使用哈希表(HashMap),其中键(key)存储数组的值,值(value)存储该值对应的最新索引

在遍历数组时,我们执行以下操作:

  1. 检查是否存在相同的值:如果 nums[i] 已经在哈希表中存在,说明之前出现过相同的值

  2. 计算索引差值:如果当前索引 i 与哈希表存储的索引之差不超过 k,则直接返回 true

  3. 更新索引:如果 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²) 复杂度,使得处理大规模数据时更加高效。

希望这篇分享能为你带来启发!如果你有任何问题或建议,欢迎在评论区留言,与我共同交流探讨。

License:  CC BY 4.0