第 478 场周赛Q3——3761. 镜像对之间最小绝对距离

题目链接：3761. 镜像对之间最小绝对距离（中等）

算法原理：

👉对应力扣题解

解法：哈希表

54ms击败77.45%

时间复杂度O(N)

①使用哈希表：既然要找两个数之间的距离，那么可以把一个存进哈希表，在遍历的时候判断两数之间能否匹配上，从而更新距离

②更新最后一次出现位置：由于要求的是最小的绝对距离，所以要更新把出现的位置更新到最后一次，从而保证距离最小而不是最大

③哈希表记录更早信息：明确哈希表中存的是什么，存的是<数，最后一次出现下标>，那么这个数是什么数呢？答案是要存“在当前位置看来，之前出现过的当前位置的数”也就是在当前位置的数看来是当前位置的数翻转过的数，为什么不存原始数，然后检查当前数翻转后是否等于原始数呢？首先明确：在当前位置看来，之前出现过的当前位置的数的位置为i，因为题目要求的是 reverse(nums[i]) == nums[j]，而咱们遍历的就是 j ，如果存之前的原始数就会变成 nums[i]==reverse(nums[j])，正好与题意要求相反，所以存进哈希表的是当前数翻转过的数

④总结以上思路：遍历数组，直接用当前数当key,检查之前是否有翻转数==key，有的话就更新最小距离，之后更新此数的翻转数的最后一次出现位置，最后检查ret是否存了最小距离，没存就代表没有符合题意的数，直接返回-1

Java代码：

class Solution { public int minMirrorPairDistance(int[] nums) { int n=nums.length; int ret=0x3f3f3f3f; //存<数,最后一次出现下标> //哈希表：记录更早的信息 Map<Integer,Integer> hash=new HashMap<>(); for(int j=0;j<n;j++){ int cur=nums[j]; //直接用当前数当key,检查之前是否有翻转数==key //如果把cur存进哈希表，然后查找cur的翻转值就会变成： //nums[i]==reverse(nums[j]) //与题目要求的reverse(nums[i]) == nums[j]相反 //就是i<j要成立，所以记录更早信息，要存cur的翻转值 if(hash.containsKey(cur)) ret=Math.min(ret,j-hash.get(cur)); hash.put(reverse(cur),j); } return ret==0x3f3f3f3f?-1:ret; } private int reverse(int n){ int ret=0; //自动去除了前导0 while(n!=0){ int t=n%10; ret=ret*10+t; n/=10; } return ret; } }