What pattern does Closest Equal Element Queries follow?

It follows the array scanning plus hash lookup pattern, combining dictionary-based preprocessing with efficient nearest index search.

How do I handle circular wrapping in the array?

Compare distances both forward and backward in the circular sense, using modulo arithmetic to wrap around the array ends.

Why is a sorted list of indices needed?

Sorting allows binary search to quickly find the nearest index, reducing query processing from O(N) to O(log K).

What should I return if no matching index exists?

Return -1 for that query to indicate no other index shares the same value.

Can this approach handle large arrays efficiently?

Yes, preprocessing with a hash map and binary search ensures the solution scales to arrays of length up to 10^5.

#3488

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

距离最小相等元素查询

给你一个环形数组 nums 和一个数组 queries 。对于每个查询 i ，你需要找到以下内容：数组 nums 中下标 queries[i] 处的元素与任意其他下标 j （满足 nums[j] == nums[queries[i]] ）之间的最小距离。如果不存在这样的下标 j ，则…

数组哈希表二分查找

题目描述

给你一个环形数组 nums 和一个数组 queries 。

对于每个查询 i ，你需要找到以下内容：

数组 nums 中下标 queries[i] 处的元素与任意其他下标 j（满足 nums[j] == nums[queries[i]]）之间的最小距离。如果不存在这样的下标 j，则该查询的结果为 -1 。

返回一个数组 answer，其大小与 queries 相同，其中 answer[i] 表示查询i的结果。

示例 1：

输入： nums = [1,3,1,4,1,3,2], queries = [0,3,5]

输出： [2,-1,3]

解释：

查询 0：下标 queries[0] = 0 处的元素为 nums[0] = 1 。最近的相同值下标为 2，距离为 2。
查询 1：下标 queries[1] = 3 处的元素为 nums[3] = 4 。不存在其他包含值 4 的下标，因此结果为 -1。
查询 2：下标 queries[2] = 5 处的元素为 nums[5] = 3 。最近的相同值下标为 1，距离为 3（沿着循环路径：5 -> 6 -> 0 -> 1）。

示例 2：

输入： nums = [1,2,3,4], queries = [0,1,2,3]

输出： [-1,-1,-1,-1]

解释：

数组 nums 中的每个值都是唯一的，因此没有下标与查询的元素值相同。所有查询的结果均为 -1。

提示：

1 <= queries.length <= nums.length <= 10⁵
1 <= nums[i] <= 10⁶
0 <= queries[i] < nums.length

lightbulb

解题思路

方法一：环形数组 + 哈希表

根据题目描述，我们需要找出数组每个元素与上一个相同元素的最小距离，以及与下一个相同元素的最小距离。并且，由于数组是循环的，所以我们需要考虑数组的环形特性，我们可以将数组扩展为原数组的两倍，然后使用哈希表 $\textit{left}$ 和 $\textit{right}$ 分别记录每个元素上一次出现的位置和下一次出现的位置，计算出每个位置的元素与另一个相同元素的最小距离，记录在数组 $\textit{d}$ 中。最后，我们遍历查询，对于每个查询 $i$ ，我们取 $\textit{d}[i]$ 和 $\textit{d}[i+n]$ 中的最小值，如果该值大于等于 $n$ ，则说明不存在与查询元素相同的元素，返回 $-1$ ，否则返回该值。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $\textit{nums}$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Solution:
    def solveQueries(self, nums: List[int], queries: List[int]) -> List[int]:
        n = len(nums)
        m = n << 1
        d = [m] * m
        left = {}
        for i in range(m):
            x = nums[i % n]
            if x in left:
                d[i] = min(d[i], i - left[x])
            left[x] = i
        right = {}
        for i in range(m - 1, -1, -1):
            x = nums[i % n]
            if x in right:
                d[i] = min(d[i], right[x] - i)
            right[x] = i
        for i in range(n):
            d[i] = min(d[i], d[i + n])
        return [-1 if d[i] >= n else d[i] for i in queries]

speed

复杂度分析

指标	值
时间	complexity is O(N + Q log K) where N is the length of nums, Q is the number of queries, and K is the frequency of the queried value. Space complexity is O(N) for the hash map storing indices.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Looking for hash-based preprocessing to avoid repeated full scans.
question_mark
Checking understanding of circular array indexing and nearest distance calculation.
question_mark
Expecting efficient O(log K) lookup per query instead of naive O(N) search.

warning

常见陷阱

外企场景

error
Forgetting to handle circular array wrapping when computing distances.
error
Scanning the entire array for each query, leading to timeouts on large inputs.
error
Neglecting to sort indices in the hash map, making binary search incorrect.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Non-circular version where array ends are not connected, simplifying distance calculation.
arrow_right_alt
Queries that ask for the farthest matching index instead of the closest.
arrow_right_alt
Dynamic updates to nums where indices mapping must be maintained after each change.

help

常见问题

外企场景

继续练习

#3508 设计路由器 #3532 针对图的路径存在性查询 I #3312 查询排序后的最大公约数