LeetCode题练习与总结：存在重复元素Ⅱ--219

本文主要是介绍LeetCode题练习与总结：存在重复元素Ⅱ--219，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、题目描述

给你一个整数数组 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

二、解题思路

使用一个哈希表（HashMap）来存储遍历过的数字及其对应的索引。
遍历数组 nums，对于每个元素 nums[i]：
- 检查当前元素是否已经在哈希表中，如果存在，则计算当前索引 i 与哈希表中存储的索引之差的绝对值，如果小于等于 k，则返回 true。
- 如果当前元素不在哈希表中，或者不满足上述条件，则将当前元素及其索引存入哈希表。
如果遍历完整个数组都没有找到满足条件的索引对，则返回 false。

三、具体代码

import java.util.HashMap;
import java.util.Map;class Solution {public boolean containsNearbyDuplicate(int[] nums, int k) {Map<Integer, Integer> map = new HashMap<>(); // 哈希表存储元素及其索引for (int i = 0; i < nums.length; i++) {// 检查当前元素是否在哈希表中，并且索引差小于等于kif (map.containsKey(nums[i]) && i - map.get(nums[i]) <= k) {return true;}// 将当前元素及其索引存入哈希表map.put(nums[i], i);}return false; // 遍历完数组没有找到满足条件的索引对}
}

这段代码中，我们使用了一个HashMap来存储数组中的元素和它们对应的索引。当我们遍历数组时，我们首先检查当前元素是否已经在HashMap中，如果是，则检查索引差是否满足条件。如果满足条件，我们返回true。如果不满足，我们将当前元素和它的索引存入HashMap。如果遍历完整个数组都没有找到满足条件的索引对，我们返回false。

四、时间复杂度和空间复杂度

1. 时间复杂度

遍历数组 nums 的时间复杂度是 O(n)，其中 n 是数组 nums 的长度。
在每次遍历时，我们会在哈希表 map 中进行两个操作：containsKey 和 put。在理想情况下，哈希表的操作时间复杂度是 O(1)，这是因为哈希表通过散列函数将键均匀分布到桶中，从而可以在常数时间内访问、插入和删除元素。

综上所述，整体算法的时间复杂度是 O(n)，因为每个元素只被处理一次，且每次处理的时间复杂度是 O(1)。

2. 空间复杂度

哈希表 map 的大小取决于数组 nums 中不同元素的数量。在最坏的情况下，如果数组中的所有元素都是唯一的，那么哈希表的大小将与数组 nums 的长度相同，即 O(n)。
哈希表中的每个条目包含一个整数（数组中的元素）和一个整数（索引），因此每个条目的大小是 O(1)。

因此，整体算法的空间复杂度是 O(n)，这是因为在最坏的情况下，我们需要存储数组中的所有元素及其索引。

五、总结知识点

类定义 (class 关键字):
- 定义了一个名为 Solution 的公共类。
方法定义:
- 定义了一个名为 containsNearbyDuplicate 的公共实例方法，接受一个整数数组 nums 和一个整数 k 作为参数，并返回一个布尔值。
数据结构 (HashMap):
- 使用了 HashMap，它是 Java 中的一个哈希表实现，用于存储键值对（在本例中是数组元素及其索引）。
循环 (for 循环):
- 使用了 for 循环来遍历数组 nums。
条件判断 (if 语句):
- 使用了 if 语句来检查是否在哈希表中找到了与当前元素相等的元素，并且索引差满足小于等于 k 的条件。
哈希表操作:
- 使用了 HashMap 的 containsKey 方法来检查哈希表中是否包含特定的键。
- 使用了 HashMap 的 get 方法来获取与特定键关联的值。
- 使用了 HashMap 的 put 方法来将键值对插入到哈希表中。