LeetCode 219. 存在重复元素 II

Categories:

题目描述
思路分析
1. 解法一：哈希表记录最近位置（推荐）
相似题目

题目描述

✅ 219. 存在重复元素 II

思路分析

解法一：哈希表记录最近位置（推荐）

核心思路：

用哈希表记录每个数字最近出现的位置。

扫描数组时，若当前索引与上次出现索引差值不超过 k，直接返回 true。

否则更新该数字的最近位置。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(n)，哈希表存储元素位置。

import java.util.*;

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, Integer> last = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            Integer prev = last.get(nums[i]);
            if (prev != null && i - prev <= k) {
                return true;
            }
            last.put(nums[i], i);
        }
        return false;
    }
}

func containsNearbyDuplicate(nums []int, k int) bool {
    last := make(map[int]int)
    for i, v := range nums {
        if prev, ok := last[v]; ok && i-prev <= k {
            return true
        }
        last[v] = i
    }
    return false
}

相似题目

题目	难度	考察点
217. 存在重复元素	简单	哈希表
220. 存在重复元素 III	困难	滑动窗口
3. 无重复字符的最长子串	中等	滑动窗口
438. 找到字符串中所有字母异位词	中等	滑动窗口
1004. 最大连续1的个数 III	中等	滑动窗口

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/43310375