【哈希】Leetcode 219. 存在重复元素 II【简单】
存在重复元素 II
- 给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，
- 满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；
- 否则，返回 false 。
示例 1：
输入：nums = [1,2,3,1], k = 3
输出：true
解题思路
- 使用哈希表（HashMap）来记录每个元素最后一次出现的索引。
- 遍历数组时，检查当前元素是否已经在哈希表中存在且索引差小于等于 k。
- 如果存在这样的元素，则返回 true；
- 如果遍历完整个数组后没有找到这样的元素，则返回 false。
Java实现
public class ContainsNearbyDuplicate {public boolean containsNearbyDuplicate(int[] nums, int k) {Map<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;}public static void main(String[] args) {ContainsNearbyDuplicate solution = new ContainsNearbyDuplicate();// Test Case 1int[] nums1 = {1, 2, 3, 1};int k1 = 3;System.out.println("Test Case 1:");System.out.println("Result: " + solution.containsNearbyDuplicate(nums1, k1)); // Expected: true// Test Case 2int[] nums2 = {1, 2, 3, 1, 2, 3};int k2 = 2;System.out.println("\nTest Case 2:");System.out.println("Result: " + solution.containsNearbyDuplicate(nums2, k2)); // Expected: false}
}时间空间复杂度
-
时间复杂度：遍历数组一次，时间复杂度为 O(n)，其中 n 是数组的长度。
-
空间复杂度：使用了一个哈希表来存储元素及其索引， 最坏情况下需要存储 n 个元素，因此空间复杂度为 O(n)