3488. 距离最小相等元素查询

题目链接：https://leetcode.cn/problems/closest-equal-element-queries/description/

根据灵茶山艾府的题解增加了注释

Java

class Solution {
   public List<Integer> solveQueries(int[] nums, int[] queries) {
       Map<Integer, List<Integer>> indices = new HashMap<>();
       // 每个数对应的出现在nums中的下标位置，存入 indices.get(nums[i]);
       for (int i = 0; i < nums.length; i++) {
           // computeIfAbsent 方法返回的是 nums[i] 对应的 List<Integer>
           // add(i) 直接在这个 List<Integer> 添加 i
           indices.computeIfAbsent(nums[i], k -> new ArrayList<>()).add(i);
       }
       int n = nums.length;
       for (List<Integer> pos : indices.values()) {
           // 该数字第一次出现在nums中的下标
           int start = pos.get(0);
           // 该数字最后一次出现在nums中的下标
           int end = pos.get(pos.size() -1);
           // 由于是循环数组, (start + n) % n = start
           // 从头向右走到尾再回到起点处, 也有一个下标即 start + n
           pos.add(start + n);
           // 从头向左走，即-1为数组末尾下标, -1往左递减直到end为止
           // 所以左侧也新增一个下标即 end - n
           pos.add(0, end - n);
       }

       List<Integer> ans = new ArrayList<>(queries.length); // 预分配空间
       for (int i : queries) {
           List<Integer> pos = indices.get(nums[i]);
           // 只出现一次 + 2个新增下标 = 3, 则不存在第二个相同值, 返回-1
           if (pos.size() == 3) {
               ans.add(-1);
           } else {
               // 在pos数组中二分查找 i的位置，即返回值 j
               int j = Collections.binarySearch(pos, i);
               // pos[j−1] 就是在 i 左边的最近位置, 小于 i
               // pos[j+1] 就是在 i 右边的最近位置, 大于 i
               ans.add(Math.min(i - pos.get(j - 1), pos.get(j + 1) - i));
           }
       }
       return ans;
   }
}