企业官网建设流程全解析

LeetCode 3488. 距离最小相等元素查询 详细技术解析

**标签：**LeetCode | 数组 | 环形数组 | 哈希表 | 预处理 | 中等难度

**核心考点：**环形数组的距离计算、哈希表预处理优化、高效查询实现（应对1e5级数据量）

**适用人群：**算法初学者、数组类题目进阶学习者、面试备战者（重点掌握预处理思想）

**前置说明：**本文将从题目拆解、思路分析、代码实现（含详细注释）、复杂度分析、边界案例、常见坑点六个维度，完整解析本题解决方案，确保新手能看懂、老手能复用，重点突破“环形距离计算”和“高效查询”两个核心难点。

一、题目深度解析

1.1 题目大意

给定一个环形数组nums 和一个查询数组 queries，对于每个查询 queries[i]，需完成以下操作：

1. 获取 queries[i] 下标对应的元素值 val = nums[queries[i]]；

2. 在数组中寻找所有与 val 相等的其他下标 j（j ≠ queries[i]）；

3. 计算 queries[i] 与每个 j 之间的最小环形距离；

4. 若不存在这样的 j，返回 -1；否则返回最小距离，最终将所有查询结果组成数组返回。

1.2 关键概念：环形数组的距离计算

本题的核心难点之一是“环形距离”的计算，与普通线性数组不同：

• 线性距离：两个下标 i 和 j（i < j）的距离为 j - i；

• 环形距离：由于数组是环形的，两个下标之间有两条路径，取较短的一条作为距离。

计算公式（设数组长度为 n）：

对于下标 i 和 j，环形距离 = min( |i - j| , n - |i - j| )

示例：数组长度 n=7，下标 5 和 1 的距离：|5-1|=4，n-|5-1|=3，因此最小距离为 3（对应示例1中查询2的结果）。

1.3 示例拆解（帮助理解）

以示例1为例：

nums = [1,3,1,4,1,3,2]，n=7；queries = [0,3,5]

1. 查询0（下标0）：val=1，所有相等元素下标为 [0,2,4]。排除自身0，剩余2和4。计算距离：

   • 0与2：|0-2|=2，n-2=5 → 最小2；

   • 0与4：|0-4|=4，n-4=3 → 最小3；

   • 最终取最小2，对应输出0的结果为2。

2. 查询1（下标3）：val=4，仅存在下标3，无其他相等元素，输出-1。

3. 查询2（下标5）：val=3，所有相等元素下标为 [1,5]。排除自身5，剩余1。计算距离：|5-1|=4，n-4=3 → 最小3，输出3。

二、解题思路推导（从暴力到优化）

2.1 暴力思路（不可行，仅作对比）

思路：对于每个查询，遍历整个数组，找到所有与当前元素相等的下标，计算环形距离，取最小值。

问题：时间复杂度 O(m*n)（m为查询数，n为数组长度），当 n 和 m 均为1e5时，总操作量达1e10，会超时，无法通过所有测试用例。

2.2 优化思路（预处理 + 哈希表 + 二分查找）

核心思想：预处理所有元素的下标位置，查询时通过二分查找快速找到最近的相等元素下标，避免遍历数组，将时间复杂度降至 O(n + m*logk)（k为每个元素的出现次数），满足1e5级数据量要求。

具体步骤：

1. 预处理：用哈希表存储每个元素对应的所有下标

   • key：数组中的元素值 val；

   • value：存储所有值为 val 的下标，按升序排列（遍历数组时自然按顺序存储，无需额外排序）。

2. 处理每个查询：

   • 获取当前查询下标 idx = queries[i]，val = nums[idx]；

   • 从哈希表中获取 val 对应的下标列表 pos_list；

   • 若 pos_list 的长度为1（仅当前下标），返回 -1；

   • 否则，在 pos_list 中找到 idx 的位置，通过二分查找找到其前一个下标和后一个下标（环形处理，首尾相连）；

   • 计算 idx 与前、后下标之间的环形距离，取最小值作为当前查询的结果。

2.3 关键优化点说明

• 哈希表预处理：将相同元素的下标集中存储，避免每次查询都遍历数组，这是性能优化的核心；

• 二分查找：下标列表是升序的，用二分查找快速定位当前 idx 在列表中的位置，时间复杂度 O(logk)（k为下标列表长度）；

• 环形处理：当下标是列表的第一个元素时，前一个下标为列表的最后一个元素；当下标是列表的最后一个元素时，后一个下标为列表的第一个元素，确保环形逻辑生效。

三、完整代码实现（含详细注释）

代码严格遵循题目要求的类和方法格式，添加详尽注释，关键步骤标注思路，可直接复制提交LeetCode，兼容Python3环境。

fromtypingimportListimportbisectclassSolution:defsolveQueries(self,nums:List[int],queries:List[int])->List[int]:# 步骤1：预处理哈希表，key为元素值，value为该元素所有下标的升序列表val_pos=dict()n=len(nums)foridx,valinenumerate(nums):ifvalnotinval_pos:val_pos[val]=[]val_pos[val].append(idx)# 步骤2：处理每个查询，存储结果answer=[]forqinqueries:val=nums[q]pos_list=val_pos[val]# 若该元素仅出现一次，直接返回-1iflen(pos_list)==1:answer.append(-1)continue# 步骤3：二分查找当前下标q在pos_list中的位置# bisect_left返回第一个大于等于q的下标，此处q一定在pos_list中，因此返回的就是q的索引idx_in_list=bisect.bisect_left(pos_list,q)m=len(pos_list)# 步骤4：找到前一个和后一个下标（环形处理）# 前一个下标：若当前是第一个元素，取最后一个；否则取前一个prev_pos=pos_list[idx_in_list-1]ifidx_in_list>0elsepos_list[-1]# 后一个下标：若当前是最后一个元素，取第一个；否则取后一个next_pos=pos_list[idx_in_list+1]ifidx_in_list<m-1elsepos_list[0]# 步骤5：计算环形距离，取最小值# 环形距离公式：min(|q - pos|, n - |q - pos|)dist_prev=min(abs(q-prev_pos),n-abs(q-prev_pos))dist_next=min(abs(q-next_pos),n-abs(q-next_pos))min_dist=min(dist_prev,dist_next)answer.append(min_dist)returnanswer

四、代码解析与复杂度分析

4.1 代码关键步骤解析

1. 哈希表预处理：遍历nums数组，将每个元素的下标存入对应的列表，确保列表是升序的（因为遍历顺序是从0到n-1，自然升序）；

2. 二分查找定位：使用bisect_left函数，快速找到当前查询下标q在pos_list中的位置，避免遍历列表，提升效率；

3. 环形下标处理：通过判断当前下标在pos_list中的位置（首尾或中间），确定前、后下标，确保环形逻辑正确；

4. 距离计算：严格按照环形距离公式计算，取前、后下标距离的最小值，作为当前查询的结果。

4.2 复杂度分析

• 时间复杂度：

  • 预处理阶段：O(n)，遍历nums数组一次，将下标存入哈希表；

  • 查询阶段：O(m*logk)，m为查询数，k为每个元素的出现次数（二分查找的时间复杂度为O(logk)）；

  • 总时间复杂度：O(n + mlogk)，满足n和m均为1e5的场景（1e5 + 1e520 = 2.1e6，远低于时间限制）。

• 空间复杂度：O(n)，哈希表存储所有元素的下标，最坏情况下（所有元素相同），pos_list的长度为n，总空间为O(n)。

五、边界案例与测试验证

5.1 边界案例（容易踩坑的场景）

1. 案例1：所有元素唯一（示例2）

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

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

   • 解析：每个元素的pos_list长度均为1，所有查询返回-1。

2. 案例2：所有元素相同（环形距离生效）

   • 输入：nums = [5,5,5,5]，queries = [0,1]

   • 输出：[1,1]

   • 解析：下标0的前一个是3（距离min(3,1)=1），后一个是1（距离1），最小为1；下标1同理。

3. 案例3：元素出现两次（环形距离取最短）

   • 输入：nums = [2,3,2]，queries = [0]

   • 输出：[1]

   • 解析：pos_list = [0,2]，距离|0-2|=2，n-2=1，取最小1。

4. 案例4：查询下标为pos_list的首尾元素

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

   • 输出：[1,1]

   • 解析：下标0的后一个是2（距离2），前一个是4（距离min(4,1)=1），最小1；下标4的前一个是2（距离2），后一个是0（距离min(4,1)=1），最小1。

5.2 测试验证

将上述案例代入代码，均可得到正确结果。提交LeetCode后，可通过所有测试用例，包括1e5级别的大数据量测试。

六、常见坑点与避坑指南

1. 坑点1：忽略环形特性，仅计算线性距离

   • 错误表现：示例1中查询2（下标5），仅计算|5-1|=4，忽略n-4=3，导致结果错误；

   • 避坑：严格使用环形距离公式 min(|i-j|, n-|i-j|)。

2. 坑点2：二分查找定位错误

   • 错误表现：使用bisect_right函数，导致定位到当前下标之后的位置；

   • 避坑：使用bisect_left函数，因为pos_list是升序且包含当前下标，bisect_left会精准定位到当前下标的索引。

3. 坑点3：首尾下标处理遗漏

   • 错误表现：当下标是pos_list的第一个元素时，未取最后一个元素作为前下标；

   • 避坑：通过判断idx_in_list是否为0或m-1，处理首尾情况，确保环形逻辑生效。

4. 坑点4：哈希表初始化遗漏

   • 错误表现：当元素第一次出现时，未初始化对应的列表，直接append导致报错；

   • 避坑：遍历nums时，先判断val是否在val_pos中，若不在则初始化空列表。

七、总结与拓展

7.1 解题总结

本题的核心是“预处理+二分查找”，通过哈希表将相同元素的下标集中存储，避免暴力遍历，再通过二分查找快速定位下标，结合环形距离公式，实现高效查询。核心考点是环形数组的特性、哈希表的应用和二分查找的优化，属于中等难度题目中典型的“预处理优化”题型。

代码的核心优势的是：时间复杂度低，适配大数据量；逻辑清晰，易于理解和复用；边界处理完善，覆盖所有易错场景。

7.2 拓展思考

• 拓展1：若题目改为“最大环形距离”，如何修改代码？

  • 思路：将min改为max，计算前、后下标距离的最大值即可。

• 拓展2：若数组不是环形，仅需线性距离，如何简化代码？

  • 思路：删除环形距离公式中的n - |i-j|，直接取|i-j|即可。

• 拓展3：如何处理重复查询（多个查询下标对应同一个元素）？

  • 思路：可新增一个缓存字典，存储已经计算过的查询结果，重复查询时直接返回缓存值，进一步优化性能。

通过本题，可重点掌握“预处理优化”的思想——对于多查询、大数据量的题目，提前将核心信息预处理好，能大幅降低查询阶段的时间复杂度，这是面试中高频考察的解题思路，建议重点掌握。