力扣经典150题第四十五题：存在重复元素 II

当然，以下是使用Java语言实现的解法，并将整篇文章以Markdown格式呈现：

力扣经典150题第四十五题：存在重复元素 II

介绍

在本文中，我们将使用Java语言解决力扣经典150题中的第四十五题，该题目要求我们判断一个整数数组中是否存在两个相同的元素，且它们的索引之差不超过给定的k值。我们将深入分析问题，并给出解题思路和具体的算法实现。

题目分析

给定一个整数数组nums和一个整数k，我们需要判断是否存在两个不同的索引i和j，满足nums[i] == nums[j]且Math.abs(i - j) <= k。

解题思路

我们可以通过哈希表来解决这个问题。具体来说，我们遍历数组nums，在遍历的过程中，我们检查当前元素是否已经在哈希表中，如果已经在哈希表中，我们计算当前索引与哈希表中存储的索引之差是否不超过k。如果满足条件，则返回true；否则，将当前元素及其索引加入哈希表中。如果遍历结束后没有找到满足条件的元素对，则返回false。

算法实现

import java.util.HashMap;

public class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        HashMap<Integer, Integer> numIndex = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (numIndex.containsKey(nums[i]) && i - numIndex.get(nums[i]) <= k) {
                return true;
            }
            numIndex.put(nums[i], i);
        }
        return false;
    }
}
## 复杂度分析
- 时间复杂度：O(n)，其中n是数组`nums`的长度。因为我们只需遍历一次数组。
- 空间复杂度：O(min(n, k))，哈希表最多存储min(n, k)个元素。

## 实例与测试
除了题目中给出的示例外，我们还可以进行更多的测试以验证算法的正确性和效率。例如：

```java
public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums1 = {1, 2, 3, 1};
        int[] nums2 = {1, 0, 1, 1};
        int[] nums3 = {1, 2, 3, 1, 2, 3};
        
        System.out.println(solution.containsNearbyDuplicate(nums1, 3)); // 输出：true
        System.out.println(solution.containsNearbyDuplicate(nums2, 1)); // 输出：true
        System.out.println(solution.containsNearbyDuplicate(nums3, 2)); // 输出：false
    }
}

通过这些示例测试，我们可以确保算法能够正确地处理各种情况，并在给定的时间复杂度内完成任务。

总结

在本文中，我们介绍了使用Java语言解决存在重复元素 II 问题的一种解题思路，并给出了具体的算法实现。通过利用哈希表，我们可以在O(n)的时间复杂度内解决该问题，其中n是数组的长度。同时，我们也对算法的复杂度进行了分析，并进行了实例测试验证。希望本文能对读者理解和掌握该问题的解题思路有所帮助。

原文地址：https://blog.csdn.net/weixin_44976692/article/details/138243721

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！