当前位置：首页 > news >正文

LeetCode 3740. 三个相等元素之间的最小距离 I, 3741. 三个相等元素之间的最小距离 II【按照相同元素分组】中等

news 2026/8/4 7:45:19

本文属于「征服LeetCode」系列文章之一，这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁，本系列将至少持续到刷完所有无锁题之日为止；由于LeetCode还在不断地创建新题，本系列的终止日期可能是永远。在这一系列刷题文章中，我不仅会讲解多种解题思路及其优化，还会用多种编程语言实现题解，涉及到通用解法时更将归纳总结出相应的算法模板。

为了方便在PC上运行调试、分享代码文件，我还建立了相关的仓库：https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中，你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等，还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解，还可以一同分享给他人。

由于本系列文章的内容随时可能发生更新变动，欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。

给你一个整数数组nums。

如果满足nums[i] == nums[j] == nums[k]，且(i, j, k)是 3 个不同下标，那么三元组(i, j, k)被称为有效三元组。

有效三元组的距离被定义为abs(i - j) + abs(j - k) + abs(k - i)，其中abs(x)表示x的绝对值。

返回一个整数，表示有效三元组的最小可能距离。如果不存在有效三元组，返回-1。

示例 1：

输入： nums=[1,2,1,1,3]输出：6

解释：最小距离对应的有效三元组是(0, 2, 3)。

(0, 2, 3)是一个有效三元组，因为nums[0] == nums[2] == nums[3] == 1。它的距离为abs(0 - 2) + abs(2 - 3) + abs(3 - 0) = 2 + 1 + 3 = 6。

示例 2：

输入： nums=[1,1,2,3,2,1,2]输出：8

解释：最小距离对应的有效三元组是(2, 4, 6)。

(2, 4, 6)是一个有效三元组，因为nums[2] == nums[4] == nums[6] == 2。它的距离为abs(2 - 4) + abs(4 - 6) + abs(6 - 2) = 2 + 2 + 4 = 8。

示例 3：

输入： nums=[1]输出：-1

解释：不存在有效三元组，因此答案为 -1。

提示：

1 <= n == nums.length <= 10^5
1 <= nums[i] <= n

解法按照相同元素分组的O ( n ) O(n)O(n)做法

按照相同元素分组，记录相同元素的下标，保存到列表中。

把i , j , k i,j,ki,j,k画在一维数轴上，∣ i − j ∣ + ∣ j − k ∣ + ∣ k − i ∣ ∣i−j∣+∣j−k∣+∣k−i∣∣i−j∣+∣j−k∣+∣k−i∣的几何意义就是这三个下标中的最左最右下标之差的两倍，设最左最右的下标分别为i ii和k kk，那么三元组的距离为2 ( k − i ) 2(k−i)2(k−i)。

为了让2 ( k − i ) 2(k−i)2(k−i)尽量小，可以取同一组中的连续三个下标分别作为i , j , k i,j,ki,j,k。计算上式的最小值，即为答案。

classSolution{publicintminimumDistance(int[]nums){Map<Integer,List<Integer>>pos=newHashMap<>();for(inti=0;i<nums.length;i++){pos.computeIfAbsent(nums[i],_->newArrayList<>()).add(i);}intans=Integer.MAX_VALUE;for(List<Integer>p:pos.values()){for(inti=2;i<p.size();i++){ans=Math.min(ans,(p.get(i)-p.get(i-2))*2);}}returnans==Integer.MAX_VALUE?-1:ans;}}

classSolution{public:intminimumDistance(vector<int>&nums){unordered_map<int,vector<int>>pos;for(inti=0;i<nums.size();i++){pos[nums[i]].push_back(i);}intans=INT_MAX;for(auto&[_,p]:pos){for(inti=2;i<p.size();i++){ans=min(ans,(p[i]-p[i-2])*2);}}returnans==INT_MAX?-1:ans;}};

classSolution:defminimumDistance(self,nums:List[int])->int:pos=defaultdict(list)fori,xinenumerate(nums):pos[x].append(i)ans=infforpinpos.values():foriinrange(2,len(p)):ans=min(ans,(p[i]-p[i-2])*2)return-1ifans==infelseans

funcminimumDistance(nums[]int)int{pos:=map[int][]int{}fori,x:=rangenums{pos[x]=append(pos[x],i)}ans:=math.MaxIntfor_,p:=rangepos{fori:=2;i<len(p);i++{ans=min(ans,(p[i]-p[i-2])*2)}}ifans==math.MaxInt{return-1}returnans}

小优化：如果n u m s numsnums包含3 33个连续相同的数，直接返回最小答案4 44。

classSolution{publicintminimumDistance(int[]nums){Map<Integer,List<Integer>>pos=newHashMap<>();for(inti=0;i<nums.length;i++){if(i>=2&&nums[i]==nums[i-1]&&nums[i]==nums[i-2]){return4;}pos.computeIfAbsent(nums[i],_->newArrayList<>()).add(i);}intans=Integer.MAX_VALUE;for(List<Integer>p:pos.values()){for(inti=2;i<p.size();i++){ans=Math.min(ans,(p.get(i)-p.get(i-2))*2);}}returnans==Integer.MAX_VALUE?-1:ans;}}

classSolution{public:intminimumDistance(vector<int>&nums){unordered_map<int,vector<int>>pos;for(inti=0;i<nums.size();i++){if(i>=2&&nums[i]==nums[i-1]&&nums[i]==nums[i-2]){return4;}pos[nums[i]].push_back(i);}intans=INT_MAX;for(auto&[_,p]:pos){for(inti=2;i<p.size();i++){ans=min(ans,(p[i]-p[i-2])*2);}}returnans==INT_MAX?-1:ans;}};

classSolution:defminimumDistance(self,nums:List[int])->int:pos=defaultdict(list)fori,xinenumerate(nums):ifi>=2andx==nums[i-1]==nums[i-2]:return4pos[x].append(i)ans=infforpinpos.values():foriinrange(2,len(p)):ans=min(ans,(p[i]-p[i-2])*2)return-1ifans==infelseans

funcminimumDistance(nums[]int)int{pos:=map[int][]int{}fori,x:=rangenums{ifi>=2&&x==nums[i-1]&&x==nums[i-2]{return4}pos[x]=append(pos[x],i)}ans:=math.MaxIntfor_,p:=rangepos{fori:=2;i<len(p);i++{ans=min(ans,(p[i]-p[i-2])*2)}}ifans==math.MaxInt{return-1}returnans}