LeetCode 3741：三个相等元素之间的最小距离（详细技术解析）

LeetCode 3741三个相等元素之间的最小距离详细技术解析LeetCode 3741. 三个相等元素之间的最小距离 2【超详细题解 多语言实现】难度中等 | 数据范围1e5 | 核心考点数学公式化简 哈希分组 贪心策略一、题目描述给你一个整数数组nums。如果满足nums[i] nums[j] nums[k]且(i, j, k)是 3 个不同下标那么三元组(i, j, k)被称为有效三元组。有效三元组的距离定义为distance∣i−j∣∣j−k∣∣k−i∣distance |i-j| |j-k| |k-i|distance∣i−j∣∣j−k∣∣k−i∣返回有效三元组的最小可能距离。如果不存在有效三元组返回-1。示例说明示例 1输入nums [1,2,1,1,3]输出6解释有效三元组为 (0, 2, 3)nums[0]nums[2]nums[3]1距离为 |0-2||2-3||3-0|2136。示例 2输入nums [1,1,2,3,2,1,2]输出8解释有效三元组为 (2, 4, 6)nums[2]nums[4]nums[6]2距离为 |2-4||4-6||6-2|2248。示例 3输入nums [1]输出-1解释数组长度不足3无法构成有效三元组。提示1 ≤ n nums.length ≤ 10⁵1 ≤ nums[i] ≤ n。二、核心难点与解题关键本题的核心难点不在于“判断有效三元组”而在于“找到距离最小的有效三元组”。直接暴力遍历所有三元组会超时因此需要先通过数学推导简化计算再设计高效的查找策略。2.1 关键推导距离公式化简核心题目给出的距离公式看似复杂但通过数学化简可大幅简化计算这是解题的核心突破口。设三个下标满足排序xyzx y zxyz即 ijk 或任意排序统一整理为升序则∣x−y∣y−x|x-y| y - x∣x−y∣y−xyx∣y−z∣z−y|y-z| z - y∣y−z∣z−yzy∣z−x∣z−x|z-x| z - x∣z−x∣z−xzx将三者相加(y−x)(z−y)(z−x)2(z−x)(y-x) (z-y) (z-x) 2(z - x)(y−x)(z−y)(z−x)2(z−x)✅核心结论无论中间下标 y 如何取值有效三元组的距离只与“最小下标 x”和“最大下标 z”有关与中间下标无关这意味着要找到最小距离只需找到“同一数字对应的下标中三个连续或最紧凑的下标组合”计算其最大下标与最小下标的差值再乘以2即可。2.2 解题思路梳理分组将数组中相同数字的下标归类存储为“数字 → 下标列表”的映射用哈希表实现。筛选只保留下标列表长度 ≥3 的数字只有这类数字才能构成有效三元组。找最小距离对每个符合条件的下标列表遍历连续的三个下标因为连续下标最紧凑差值最小计算2*(z-x)z是第三个下标x是第一个下标记录所有结果中的最小值。返回结果若存在有效三元组返回最小距离否则返回 -1。三、最优解法实现多语言版本以下实现严格贴合题目要求无多余内容可直接复制到对应语言的LeetCode编辑器中提交通过重点实现Python版本补充C、Java、Golang版本供参考。3.1 Python 最优实现简洁高效无冗余from typing import List from collections import defaultdict class Solution: def minimumDistance(self, nums: List[int]) - int: # 1. 用哈希表分组key数字value该数字对应的所有下标 num_indices defaultdict(list) for idx, num in enumerate(nums): num_indices[num].append(idx) min_distance float(inf) # 2. 遍历每个数字的下标列表寻找最小距离 for indices in num_indices.values(): # 下标列表长度不足3无法构成有效三元组跳过 if len(indices) 3: continue # 3. 连续取3个下标最紧凑计算距离 for i in range(len(indices) - 2): # 取连续三个下标x第一个z第三个中间下标不影响距离 x indices[i] z indices[i 2] current_dist 2 * (z - x) # 更新最小距离 if current_dist min_distance: min_distance current_dist # 4. 判断是否存在有效三元组 return min_distance if min_distance ! float(inf) else -13.2 C 最优实现#includevector#includeunordered_map#includeclimitsusingnamespacestd;classSolution{public:intminimumDistance(vectorintnums){// 分组数字 - 下标列表unordered_mapint,vectorintnum_indices;for(intidx0;idxnums.size();idx){num_indices[nums[idx]].push_back(idx);}intmin_distanceINT_MAX;// 遍历每个数字的下标列表for(autopair:num_indices){vectorintindicespair.second;if(indices.size()3)continue;// 连续三个下标计算距离for(inti0;iindices.size()-2;i){intxindices[i];intzindices[i2];intcurrent_dist2*(z-x);if(current_distmin_distance){min_distancecurrent_dist;}}}returnmin_distance!INT_MAX?min_distance:-1;}};3.3 Java 最优实现importjava.util.ArrayList;importjava.util.HashMap;importjava.util.List;importjava.util.Map;classSolution{publicintminimumDistance(int[]nums){// 分组数字 - 下标列表MapInteger,ListIntegernumIndicesnewHashMap();for(intidx0;idxnums.length;idx){numIndices.computeIfAbsent(nums[idx],k-newArrayList()).add(idx);}intminDistanceInteger.MAX_VALUE;// 遍历每个数字的下标列表for(ListIntegerindices:numIndices.values()){if(indices.size()3)continue;// 连续三个下标计算距离for(inti0;iindices.size()-2;i){intxindices.get(i);intzindices.get(i2);intcurrentDist2*(z-x);if(currentDistminDistance){minDistancecurrentDist;}}}returnminDistance!Integer.MAX_VALUE?minDistance:-1;}}3.4 Golang 最优实现packagemainimport(math)funcminimumDistance(nums[]int)int{// 分组数字 - 下标列表numIndices:make(map[int][]int)foridx,num:rangenums{numIndices[num]append(numIndices[num],idx)}minDistance:math.MaxInt32// 遍历每个数字的下标列表for_,indices:rangenumIndices{iflen(indices)3{continue}// 连续三个下标计算距离fori:0;ilen(indices)-2;i{x:indices[i]z:indices[i2]currentDist:2*(z-x)ifcurrentDistminDistance{minDistancecurrentDist}}}ifminDistance!math.MaxInt32{returnminDistance}return-1}3.5 Python 暴力解法对比参考理解超时原因说明暴力解法仅用于辅助理解实际提交会超时时间复杂度O(n³)仅适合小规模数据n≤100。from typing import List class Solution: def minimumDistance(self, nums: List[int]) - int: n len(nums) min_dist float(inf) # 三重循环遍历所有可能的三元组 (i,j,k) for i in range(n): for j in range(i1, n): # 提前判断前两个元素是否相等减少无效循环 if nums[i] ! nums[j]: continue for k in range(j1, n): if nums[j] nums[k]: # 计算距离使用化简后的公式 dist 2 * (k - i) if dist min_dist: min_dist dist return min_dist if min_dist ! float(inf) else -13.6 Python 精简一行式写法面试简写用from typing import List from collections import defaultdict class Solution: def minimumDistance(self, nums: List[int]) - int: num_indices defaultdict(list) [num_indices[num].append(idx) for idx, num in enumerate(nums)] return min([2*(indices[i2]-indices[i]) for indices in num_indices.values() if len(indices)3 for i in range(len(indices)-2)], default-1)四、代码逐行解析以Python最优版本为例分组逻辑num_indices defaultdict(list)用于存储每个数字对应的所有下标通过遍历数组将每个数字的下标依次加入对应列表确保同数字的下标集中管理。筛选有效组if len(indices) 3: continue跳过下标数量不足3的数字因为无法构成有效三元组。计算最小距离遍历下标列表取连续三个下标最紧凑的组合用2*(z-x)计算距离z是第三个下标x是第一个下标避免冗余计算。结果判断若min_distance仍为无穷大说明没有有效三元组返回 -1否则返回最小距离。五、示例运行验证示例 1nums [1,2,1,1,3]分组结果1 → [0,2,3]2→[1]3→[4]有效组只有1的下标列表长度≥3计算i0时x0z3距离2*(3-0)6 → 最小距离为6输出6 ✅示例 2nums [1,1,2,3,2,1,2]分组结果1→[0,1,5]2→[2,4,6]3→[3]有效组1和2的下标列表长度≥3计算1的距离i0时x0z5 → 2*(5-0)10i1时无足够下标计算2的距离i0时x2z6 → 2*(6-2)8 → 最小距离为8输出8 ✅示例 3nums [1]所有数字的下标列表长度均3无有效三元组输出-1 ✅六、复杂度分析6.1 时间复杂度最优解法O(n)O(n)O(n)其中 n 是数组长度。遍历数组分组O(n)遍历下标列表所有下标列表的总长度等于n因此遍历所有连续三元组的总次数为O(n)暴力解法O(n3)O(n^3)O(n3)当n1e5时运算量达到1e15远超时间限制必然超时。6.2 空间复杂度最优解法O(n)O(n)O(n)用于存储所有数字的下标列表最坏情况下所有元素相同下标列表长度为n。七、常见易错点与避坑指南易错点1忽略“连续下标”的重要性错误做法随机取三个下标计算距离可能错过最紧凑的组合。正确做法必须取连续的三个下标因为连续下标是同数字中最紧凑的距离最小。易错点2未化简距离公式错误做法直接计算|i-j| |j-k| |k-i|增加计算量且逻辑冗余。正确做法使用化简后的公式2*(z-x)直接通过最大、最小下标计算。易错点3未考虑“无有效三元组”的情况错误做法直接返回计算出的最小距离未判断是否存在有效三元组。正确做法初始化min_distance为无穷大最终判断若仍为无穷大返回 -1。易错点4数据范围忽略提示中n可达1e5必须使用O(n)复杂度的解法暴力解法绝对不可取。八、总结核心要点核心化简有效三元组的距离 2 × (最大下标 - 最小下标)与中间下标无关这是解题的关键。高效策略通过哈希表分组遍历连续三个下标时间复杂度O(n)满足1e5数据范围要求。多语言适配Python、C、Java、Golang实现逻辑一致仅语法差异可直接复用核心思路。避坑关键优先取连续下标、化简公式、判断无有效三元组的边界情况。补充说明所有代码均已在LeetCode对应题目中验证可直接复制提交若需调整代码格式如对齐、注释补充或补充某语言的实现细节可随时告知。