LeetCode 题解工作台
存在重复元素 II
给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) 。如果存在，返回 true ；否则，返回 false 。 示例 1： 输入： nums = [1,2,3,1], k = 3 输出： …
3
题型
8
代码语言
3
相关题
当前训练重点
简单 · 数组·哈希·扫描
答案摘要
我们用一个哈希表 存放最近遍历到的数以及对应的下标。 遍历数组 ，对于当前遍历到的元素 ，如果在哈希表中存在，并且下标与当前元素的下标之差不超过 ，则返回 ，否则将当前元素加入哈希表中。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个整数数组 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 <= 105-109 <= nums[i] <= 1090 <= k <= 105
解题思路
方法一：哈希表
我们用一个哈希表 存放最近遍历到的数以及对应的下标。
遍历数组 ，对于当前遍历到的元素 ，如果在哈希表中存在，并且下标与当前元素的下标之差不超过 ，则返回 ，否则将当前元素加入哈希表中。
遍历结束后，返回 。
时间复杂度 ，空间复杂度 。其中 为数组 的长度。
class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
d = {}
for i, x in enumerate(nums):
if x in d and i - d[x] <= k:
return True
d[x] = i
return False
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) for the hash map or set sliding window approach because each element is processed once and hash operations are O(1). Space complexity is O(min(n,k)) as only the most recent k elements are stored in the hash map or set, keeping memory proportional to the sliding window. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Do you understand why a hash map is necessary instead of nested loops?
- question_mark
Notice how the sliding window maintains the k-index constraint efficiently.
- question_mark
Ask if the solution handles edge cases like k = 0 or all unique elements.
常见陷阱
外企场景- error
Using nested loops blindly leads to TLE on large arrays.
- error
Failing to remove elements outside the k-window from the map or set breaks correctness.
- error
Confusing the requirement for indices versus values can result in false positives.
进阶变体
外企场景- arrow_right_alt
Check for duplicates within k distance but allow a value to repeat multiple times; count total pairs.
- arrow_right_alt
Find the first duplicate within k indices and return its pair of indices instead of true/false.
- arrow_right_alt
Extend the problem to handle multiple k values dynamically for streaming input arrays.