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

LeetCode 3488. 距离最小相等元素查询 详细技术解析**标签**LeetCode | 数组 | 环形数组 | 哈希表 | 预处理 | 中等难度**核心考点**环形数组的距离计算、哈希表预处理优化、高效查询实现应对1e5级数据量**适用人群**算法初学者、数组类题目进阶学习者、面试备战者重点掌握预处理思想**前置说明**本文将从题目拆解、思路分析、代码实现含详细注释、复杂度分析、边界案例、常见坑点六个维度完整解析本题解决方案确保新手能看懂、老手能复用重点突破“环形距离计算”和“高效查询”两个核心难点。一、题目深度解析1.1 题目大意给定一个环形数组nums 和一个查询数组 queries对于每个查询 queries[i]需完成以下操作获取 queries[i] 下标对应的元素值 val nums[queries[i]]在数组中寻找所有与 val 相等的其他下标 jj ≠ queries[i]计算 queries[i] 与每个 j 之间的最小环形距离若不存在这样的 j返回 -1否则返回最小距离最终将所有查询结果组成数组返回。1.2 关键概念环形数组的距离计算本题的核心难点之一是“环形距离”的计算与普通线性数组不同线性距离两个下标 i 和 ji j的距离为 j - i环形距离由于数组是环形的两个下标之间有两条路径取较短的一条作为距离。计算公式设数组长度为 n对于下标 i 和 j环形距离 min( |i - j| , n - |i - j| )示例数组长度 n7下标 5 和 1 的距离|5-1|4n-|5-1|3因此最小距离为 3对应示例1中查询2的结果。1.3 示例拆解帮助理解以示例1为例nums [1,3,1,4,1,3,2]n7queries [0,3,5]查询0下标0val1所有相等元素下标为 [0,2,4]。排除自身0剩余2和4。计算距离0与2|0-2|2n-25 → 最小20与4|0-4|4n-43 → 最小3最终取最小2对应输出0的结果为2。查询1下标3val4仅存在下标3无其他相等元素输出-1。查询2下标5val3所有相等元素下标为 [1,5]。排除自身5剩余1。计算距离|5-1|4n-43 → 最小3输出3。二、解题思路推导从暴力到优化2.1 暴力思路不可行仅作对比思路对于每个查询遍历整个数组找到所有与当前元素相等的下标计算环形距离取最小值。问题时间复杂度 O(m*n)m为查询数n为数组长度当 n 和 m 均为1e5时总操作量达1e10会超时无法通过所有测试用例。2.2 优化思路预处理 哈希表 二分查找核心思想预处理所有元素的下标位置查询时通过二分查找快速找到最近的相等元素下标避免遍历数组将时间复杂度降至 O(n m*logk)k为每个元素的出现次数满足1e5级数据量要求。具体步骤预处理用哈希表存储每个元素对应的所有下标key数组中的元素值 valvalue存储所有值为 val 的下标按升序排列遍历数组时自然按顺序存储无需额外排序。处理每个查询获取当前查询下标 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_posdict()nlen(nums)foridx,valinenumerate(nums):ifvalnotinval_pos:val_pos[val][]val_pos[val].append(idx)# 步骤2处理每个查询存储结果answer[]forqinqueries:valnums[q]pos_listval_pos[val]# 若该元素仅出现一次直接返回-1iflen(pos_list)1:answer.append(-1)continue# 步骤3二分查找当前下标q在pos_list中的位置# bisect_left返回第一个大于等于q的下标此处q一定在pos_list中因此返回的就是q的索引idx_in_listbisect.bisect_left(pos_list,q)mlen(pos_list)# 步骤4找到前一个和后一个下标环形处理# 前一个下标若当前是第一个元素取最后一个否则取前一个prev_pospos_list[idx_in_list-1]ifidx_in_list0elsepos_list[-1]# 后一个下标若当前是最后一个元素取第一个否则取后一个next_pospos_list[idx_in_list1]ifidx_in_listm-1elsepos_list[0]# 步骤5计算环形距离取最小值# 环形距离公式min(|q - pos|, n - |q - pos|)dist_prevmin(abs(q-prev_pos),n-abs(q-prev_pos))dist_nextmin(abs(q-next_pos),n-abs(q-next_pos))min_distmin(dist_prev,dist_next)answer.append(min_dist)returnanswer四、代码解析与复杂度分析4.1 代码关键步骤解析哈希表预处理遍历nums数组将每个元素的下标存入对应的列表确保列表是升序的因为遍历顺序是从0到n-1自然升序二分查找定位使用bisect_left函数快速找到当前查询下标q在pos_list中的位置避免遍历列表提升效率环形下标处理通过判断当前下标在pos_list中的位置首尾或中间确定前、后下标确保环形逻辑正确距离计算严格按照环形距离公式计算取前、后下标距离的最小值作为当前查询的结果。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所有元素唯一示例2输入nums [1,2,3,4]queries [0,1,2,3]输出[-1,-1,-1,-1]解析每个元素的pos_list长度均为1所有查询返回-1。案例2所有元素相同环形距离生效输入nums [5,5,5,5]queries [0,1]输出[1,1]解析下标0的前一个是3距离min(3,1)1后一个是1距离1最小为1下标1同理。案例3元素出现两次环形距离取最短输入nums [2,3,2]queries [0]输出[1]解析pos_list [0,2]距离|0-2|2n-21取最小1。案例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中查询2下标5仅计算|5-1|4忽略n-43导致结果错误避坑严格使用环形距离公式 min(|i-j|, n-|i-j|)。坑点2二分查找定位错误错误表现使用bisect_right函数导致定位到当前下标之后的位置避坑使用bisect_left函数因为pos_list是升序且包含当前下标bisect_left会精准定位到当前下标的索引。坑点3首尾下标处理遗漏错误表现当下标是pos_list的第一个元素时未取最后一个元素作为前下标避坑通过判断idx_in_list是否为0或m-1处理首尾情况确保环形逻辑生效。坑点4哈希表初始化遗漏错误表现当元素第一次出现时未初始化对应的列表直接append导致报错避坑遍历nums时先判断val是否在val_pos中若不在则初始化空列表。七、总结与拓展7.1 解题总结本题的核心是“预处理二分查找”通过哈希表将相同元素的下标集中存储避免暴力遍历再通过二分查找快速定位下标结合环形距离公式实现高效查询。核心考点是环形数组的特性、哈希表的应用和二分查找的优化属于中等难度题目中典型的“预处理优化”题型。代码的核心优势的是时间复杂度低适配大数据量逻辑清晰易于理解和复用边界处理完善覆盖所有易错场景。7.2 拓展思考拓展1若题目改为“最大环形距离”如何修改代码思路将min改为max计算前、后下标距离的最大值即可。拓展2若数组不是环形仅需线性距离如何简化代码思路删除环形距离公式中的n - |i-j|直接取|i-j|即可。拓展3如何处理重复查询多个查询下标对应同一个元素思路可新增一个缓存字典存储已经计算过的查询结果重复查询时直接返回缓存值进一步优化性能。通过本题可重点掌握“预处理优化”的思想——对于多查询、大数据量的题目提前将核心信息预处理好能大幅降低查询阶段的时间复杂度这是面试中高频考察的解题思路建议重点掌握。