LC219. 存在重复元素II

LC219. 存在重复元素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^5 -109 <= nums[i] <= 10^9 0 <= k <= 10^5

题目解析

解题思路

题目要求判断数组中是否存在两个相同元素，且它们的索引差不超过 k。核心思路是用哈希表记录每个元素最近一次出现的索引，在遍历数组时，若当前元素已在哈希表中，则检查当前索引与之前索引的差值是否 ≤ k，若满足则直接返回 true；否则更新该元素的最新索引。遍历结束后未找到则返回 false。

数据结构：哈希表（Python 字典），键为元素值，值为该元素最近一次出现的索引。

算法：一次线性扫描，利用哈希表进行快速查找。

关键步骤

1. 初始化：创建空字典 pos。 2. 遍历数组：使用 enumerate 同时获取索引 i 和元素值 v。 3. 检查重复：

• 若 v 已在 pos 中，且 i - pos[v] <= k，则找到满足条件的索引对，返回 true。
• 否则，更新 pos[v] = i（无论是否满足条件，都要更新为最新索引，因为后续可能用更近的索引判断）。

4. 遍历结束：返回 false。

示意图（以 nums=[1,2,3,1], k=3 为例）：

i=0, v=1: pos={} → 未找到，更新 pos[1]=0
i=1, v=2: pos={1:0} → 未找到，更新 pos[2]=1
i=2, v=3: pos={1:0,2:1} → 未找到，更新 pos[3]=2
i=3, v=1: pos[1]=0, i-0=3 ≤ k=3 → 返回 true

复杂度分析

• 时间复杂度：O(n)，其中 n 为数组长度。只需一次遍历，哈希表查找和插入均为 O(1)。
• 空间复杂度：O(min(n, k))。哈希表最多存储 min(n, k) 个元素（实际最坏情况存储所有不同元素，但题目保证 k 可能很大，因此最坏为 O(n)）。