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

本文属于「征服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^51 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){MapInteger,ListIntegerposnewHashMap();for(inti0;inums.length;i){pos.computeIfAbsent(nums[i],_-newArrayList()).add(i);}intansInteger.MAX_VALUE;for(ListIntegerp:pos.values()){for(inti2;ip.size();i){ansMath.min(ans,(p.get(i)-p.get(i-2))*2);}}returnansInteger.MAX_VALUE?-1:ans;}}classSolution{public:intminimumDistance(vectorintnums){unordered_mapint,vectorintpos;for(inti0;inums.size();i){pos[nums[i]].push_back(i);}intansINT_MAX;for(auto[_,p]:pos){for(inti2;ip.size();i){ansmin(ans,(p[i]-p[i-2])*2);}}returnansINT_MAX?-1:ans;}};classSolution:defminimumDistance(self,nums:List[int])-int:posdefaultdict(list)fori,xinenumerate(nums):pos[x].append(i)ansinfforpinpos.values():foriinrange(2,len(p)):ansmin(ans,(p[i]-p[i-2])*2)return-1ifansinfelseansfuncminimumDistance(nums[]int)int{pos:map[int][]int{}fori,x:rangenums{pos[x]append(pos[x],i)}ans:math.MaxIntfor_,p:rangepos{fori:2;ilen(p);i{ansmin(ans,(p[i]-p[i-2])*2)}}ifansmath.MaxInt{return-1}returnans}小优化如果n u m s numsnums包含3 33个连续相同的数直接返回最小答案4 44。classSolution{publicintminimumDistance(int[]nums){MapInteger,ListIntegerposnewHashMap();for(inti0;inums.length;i){if(i2nums[i]nums[i-1]nums[i]nums[i-2]){return4;}pos.computeIfAbsent(nums[i],_-newArrayList()).add(i);}intansInteger.MAX_VALUE;for(ListIntegerp:pos.values()){for(inti2;ip.size();i){ansMath.min(ans,(p.get(i)-p.get(i-2))*2);}}returnansInteger.MAX_VALUE?-1:ans;}}classSolution{public:intminimumDistance(vectorintnums){unordered_mapint,vectorintpos;for(inti0;inums.size();i){if(i2nums[i]nums[i-1]nums[i]nums[i-2]){return4;}pos[nums[i]].push_back(i);}intansINT_MAX;for(auto[_,p]:pos){for(inti2;ip.size();i){ansmin(ans,(p[i]-p[i-2])*2);}}returnansINT_MAX?-1:ans;}};classSolution:defminimumDistance(self,nums:List[int])-int:posdefaultdict(list)fori,xinenumerate(nums):ifi2andxnums[i-1]nums[i-2]:return4pos[x].append(i)ansinfforpinpos.values():foriinrange(2,len(p)):ansmin(ans,(p[i]-p[i-2])*2)return-1ifansinfelseansfuncminimumDistance(nums[]int)int{pos:map[int][]int{}fori,x:rangenums{ifi2xnums[i-1]xnums[i-2]{return4}pos[x]append(pos[x],i)}ans:math.MaxIntfor_,p:rangepos{fori:2;ilen(p);i{ansmin(ans,(p[i]-p[i-2])*2)}}ifansmath.MaxInt{return-1}returnans}复杂度分析时间复杂度O ( n ) O(n)O(n)其中n nn是n u m s numsnums的长度。空间复杂度O ( n ) O(n)O(n)。