存在重复元素 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⁵
-10⁹ <= nums[i] <= 10⁹
0 <= k <= 10⁵

代码结果

运行时间: 40 ms, 内存: 30.3 MB

/*
 * 思路：
 * 1. 使用Java Stream API和辅助类来实现相同的逻辑。
 * 2. 仍然需要一个哈希表来存储索引。
 * 3. 使用forEach方法遍历数组并更新哈希表。
 */
import java.util.HashMap;
import java.util.stream.IntStream;
 
public class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        return IntStream.range(0, nums.length).anyMatch(i -> {
            if (map.containsKey(nums[i]) && i - map.get(nums[i]) <= k) {
                return true;
            }
            map.put(nums[i], i);
            return false;
        });
    }
}

解释

方法:

题解的思路是使用哈希表来存储每个元素最后一次出现的下标。遍历数组，对于当前元素，如果它在哈希表中出现过，并且当前下标与哈希表中存储的下标之差小于等于 k，则说明存在重复元素，返回 True。否则，将当前元素和下标存入哈希表中。如果遍历完整个数组都没有找到满足条件的重复元素，则返回 False。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆

为什么在开始遍历数组之前，首先检查数组和去重后的集合长度是否相等？这一步是否必要？

▷

这一步是为了快速检测数组中是否存在任何重复元素。如果数组长度与去重后的集合长度相等，说明数组中所有元素都是唯一的，因此不可能存在两个相同的元素其下标之差小于或等于k。这一步虽然增加了一次完整数组的遍历，但可以在某些情况下提早结束程序，避免不必要的后续处理，特别是在大数据集中可能带来性能优势。然而，这并非必须步骤，因为主要的逻辑仍需遍历数组来检查具体的下标差条件。

🦆

在哈希表中存储元素最后一次出现的下标时，为什么不需要考虑该元素之前的下标信息？

▷

在这个问题的上下文中，我们只关心元素的最近一次出现，因为我们需要的是计算当前下标与最近一次出现下标的差值。如果这个差值小于等于k，则满足题目条件，立即返回True。更新哈希表中存储的下标为最新下标，是因为这个新的下标在后续的遍历中可能会有更近的差值满足条件。之前的下标信息不再需要，因为我们只关注最近的差值是否满足条件。

🦆

如果下标之差大于k，但是后续又出现同一元素的情况，原有的哈希表如何处理这种更新？

▷

如果在哈希表中找到了当前元素，但其存储的下标与当前下标的差大于k，我们仍会更新这个元素在哈希表中的下标为当前下标。这样做确保了每个元素在哈希表中的下标始终是其最后一次出现的下标。这个更新是必要的，因为它可能影响后续其他元素检查的结果，确保每次比较都是基于最近的下标信息，从而正确判断是否存在符合条件的重复元素。

🦆

在极端情况下，例如 k 的值非常大，接近数组长度 n，这种方法的效率如何？会有什么潜在的性能问题？

▷

当k的值非常大时，接近数组长度n，这种方法在某些情况下可能会导致性能问题。尽管最坏情况下的时间复杂度仍为O(n)，因为每个元素仍然只是简单地查找并更新哈希表，但是当k非常大时，几乎每个元素都可能在哈希表中找到匹配且其下标差小于等于k，这可以导致在遍历过程中频繁的返回True，特别是在重复元素较多的数组中。此外，存储大量元素的哈希表可能需要更多的内存空间，且在哈希表中查找和更新元素的操作虽然平均是O(1)，在极端情况下可能会接近O(n)，尤其是在哈希冲突较多的情况下。

相关问题