shelterofly

目标

给你一个下标从 0 开始的整数数组 nums 。现有一个长度等于 nums.length 的数组 arr 。对于满足 nums[j] == nums[i] 且 j != i 的所有 j ，arr[i] 等于所有 |i - j| 之和。如果不存在这样的 j ，则令 arr[i] 等于 0 。

返回数组 arr 。

示例 1：

输入：nums = [1,3,1,1,2]
输出：[5,0,3,4,0]
解释：
i = 0 ，nums[0] == nums[2] 且 nums[0] == nums[3] 。因此，arr[0] = |0 - 2| + |0 - 3| = 5 。 
i = 1 ，arr[1] = 0 因为不存在值等于 3 的其他下标。
i = 2 ，nums[2] == nums[0] 且 nums[2] == nums[3] 。因此，arr[2] = |2 - 0| + |2 - 3| = 3 。
i = 3 ，nums[3] == nums[0] 且 nums[3] == nums[2] 。因此，arr[3] = |3 - 0| + |3 - 2| = 4 。 
i = 4 ，arr[4] = 0 因为不存在值等于 2 的其他下标。

示例 2：

输入：nums = [0,5,3]
输出：[0,0,0]
解释：因为 nums 中的元素互不相同，对于所有 i ，都有 arr[i] = 0 。

说明：

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^9

思路

有一个整数数组 nums，返回一个等长数组 arr，arr[i] 等于所有与 nums[i] 相等的 nums[j] 到下标 i 的距离之和，即 Σ|i - j|，如果不存在这样的 j 则距离为 0。

使用哈希表将元素分组，假定某一组内的元素为 a0 < a1 < …… < a_(m - 1)，令 S0 = Σ_(j ∈ [0, m - 1])(aj - a0)，考虑 S1 - S0，原来所有元素到 a0 的距离变成了所有元素到 a1 的距离：组内下标小于 1 的距离都增加了 a1 - a0，组内下标大于等于 1 的距离都减少了 a1 - a0。

更一般的情况 Si - S_(i - 1)，组内下标小于 i 的元素到 a_(i - 1) 的距离都增加了 a_i - a_(i - 1)，组内下标大于等于 i 的元素到 a_(i - 1) 的距离都减小了 a_i - a_(i - 1)。组内下标小于 i 的元素有 i 个，组内下标大于等于 i 的元素有 m - i 个，Si - S_(i - 1) = i * (ai - a_(i - 1)) - (m - i) * (ai - a_(i - 1)) = (2 * i - m) * (ai - a_(i - 1))。

代码

/**
 * @date 2026-04-23 9:46
 */
public class Distance2615 {

    public long[] distance(int[] nums) {
        int n = nums.length;
        long[] res = new long[n];
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.putIfAbsent(nums[i], new ArrayList<>());
            map.get(nums[i]).add(i);
        }
        for (List<Integer> list : map.values()) {
            if (list.size() > 1) {
                long s = 0L;
                int start = list.get(0);
                for (int i = 1; i < list.size(); i++) {
                    s += list.get(i) - start;
                }
                res[start] = s;
                for (int i = 1; i < list.size(); i++) {
                    res[list.get(i)] = res[list.get(i - 1)] + (2 * i - list.size()) * (list.get(i) - list.get(i - 1));
                }
            }
        }
        return res;
    }
}

性能

目标

给你两个字符串数组 queries 和 dictionary 。数组中所有单词都只包含小写英文字母，且长度都相同。

一次 编辑 中，你可以从 queries 中选择一个单词，将任意一个字母修改成任何其他字母。从 queries 中找到所有满足以下条件的字符串：不超过 两次编辑内，字符串与 dictionary 中某个字符串相同。

请你返回 queries 中的单词列表，这些单词距离 dictionary 中的单词 编辑次数 不超过 两次 。单词返回的顺序需要与 queries 中原本顺序相同。

示例 1：

输入：queries = ["word","note","ants","wood"], dictionary = ["wood","joke","moat"]
输出：["word","note","wood"]
解释：
- 将 "word" 中的 'r' 换成 'o' ，得到 dictionary 中的单词 "wood" 。
- 将 "note" 中的 'n' 换成 'j' 且将 't' 换成 'k' ，得到 "joke" 。
- "ants" 需要超过 2 次编辑才能得到 dictionary 中的单词。
- "wood" 不需要修改（0 次编辑），就得到 dictionary 中相同的单词。
所以我们返回 ["word","note","wood"] 。

示例 2：

输入：queries = ["yes"], dictionary = ["not"]
输出：[]
解释：
"yes" 需要超过 2 次编辑才能得到 "not" 。
所以我们返回空数组。

说明：

• 1 <= queries.length, dictionary.length <= 100
• n == queries[i].length == dictionary[j].length
• 1 <= n <= 100
• 所有 queries[i] 和 dictionary[j] 都只包含小写英文字母。

思路

有两个字符串数组 queries 和 dictionary，它们的字符串长度都相等，每次编辑可以将 queries 中的任意字符串的任意一个字母改成其它字母，按 queries 顺序返回最多两次编辑能够与 dictionary 中某个字符串相同的 queries[i]。

暴力枚举，比较 queries[i] 与 dictionary 中的每个字符串不同的字符个数，如果小于等于 2 加入结果集合。

代码

/**
 * @date 2026-04-22 9:04
 */
public class TwoEditWords2452 {

    public List<String> twoEditWords_v2(String[] queries, String[] dictionary) {
        List<String> res = new ArrayList<>();
        for (String query : queries) {
            if (check(query, dictionary)) {
                res.add(query);
            }
        }
        return res;
    }

    public boolean check(String query, String[] dictionary) {
        for (String dict : dictionary) {
            int dis = 0;
            for (int k = 0; k < dict.length() && dis <= 2; k++) {
                if (query.charAt(k) != dict.charAt(k)) {
                    dis++;
                }
            }
            if (dis <= 2) {
                return true;
            }
        }
        return false;
    }

}

性能

目标

给你两个 非递增 的整数数组 nums1 和 nums2 ，数组下标均 从 0 开始 计数。

下标对 (i, j) 中 0 <= i < nums1.length 且 0 <= j < nums2.length 。如果该下标对同时满足 i <= j 且 nums1[i] <= nums2[j] ，则称之为 有效 下标对，该下标对的 距离 为 j - i 。

返回所有 有效 下标对 (i, j) 中的 最大距离 。如果不存在有效下标对，返回 0 。

一个数组 arr ，如果每个 1 <= i < arr.length 均有 arr[i-1] >= arr[i] 成立，那么该数组是一个 非递增 数组。

示例 1：

输入：nums1 = [55,30,5,4,2], nums2 = [100,20,10,10,5]
输出：2
解释：有效下标对是 (0,0), (2,2), (2,3), (2,4), (3,3), (3,4) 和 (4,4) 。
最大距离是 2 ，对应下标对 (2,4) 。

示例 2：

输入：nums1 = [2,2,2], nums2 = [10,10,1]
输出：1
解释：有效下标对是 (0,0), (0,1) 和 (1,1) 。
最大距离是 1 ，对应下标对 (0,1) 。

示例 3：

输入：nums1 = [30,29,19,5], nums2 = [25,25,25,25,25]
输出：2
解释：有效下标对是 (2,2), (2,3), (2,4), (3,3) 和 (3,4) 。
最大距离是 2 ，对应下标对 (2,4) 。

说明：

• 1 <= nums1.length <= 10^5
• 1 <= nums2.length <= 10^5
• 1 <= nums1[i], nums2[j] <= 10^5
• nums1 和 nums2 都是 非递增 数组

思路

有两个非递增的整数数组 nums1 和 nums2，返回有效下标对的最大距离，如果不存在有效下标对，返回 0。有效下标对 (i, j) 需要满足 i <= j && nums1[i] <= nums2[j]。

二分查找 nums2 大于等于 nums1[i] 的最大下标，记录 j - i 的最大值。

代码

/**
 * @date 2026-04-19 23:44
 */
public class MaxDistance1855 {

    public int maxDistance(int[] nums1, int[] nums2) {
        int res = 0;
        for (int i = 0; i < nums1.length; i++) {
            int j = upperBound(nums2, i, nums1[i]);
            res = Math.max(res, j - i);
        }
        return res;
    }

    public int upperBound(int[] arr, int l, int target) {
        int r = arr.length - 1;
        int m = l + (r - l) / 2;
        while (l <= r) {
            if (arr[m] >= target) {
                l = m + 1;
            } else {
                r = m - 1;
            }
            m = l + (r - l) / 2;
        }
        return r;
    }
}

性能

目标

给你一个整数数组 nums。

镜像对 是指一对满足下述条件的下标 (i, j)：

• 0 <= i < j < nums.length，并且
• reverse(nums[i]) == nums[j]，其中 reverse(x) 表示将整数 x 的数字反转后形成的整数。反转后会忽略前导零，例如 reverse(120) = 21。

返回任意镜像对的下标之间的 最小绝对距离。下标 i 和 j 之间的绝对距离为 abs(i - j)。

如果不存在镜像对，返回 -1。

示例 1：

输入： nums = [12,21,45,33,54]
输出： 1
解释：
镜像对为：
(0, 1)，因为 reverse(nums[0]) = reverse(12) = 21 = nums[1]，绝对距离为 abs(0 - 1) = 1。
(2, 4)，因为 reverse(nums[2]) = reverse(45) = 54 = nums[4]，绝对距离为 abs(2 - 4) = 2。
所有镜像对中的最小绝对距离是 1。

示例 2：

输入： nums = [120,21]
输出： 1
解释：
只有一个镜像对 (0, 1)，因为 reverse(nums[0]) = reverse(120) = 21 = nums[1]。
最小绝对距离是 1。

示例 3：

输入： nums = [21,120]
输出： -1
解释：
数组中不存在镜像对。

说明：

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

思路

有一个整数数组 nums，镜像对指满足条件的下标对 (i, j)，0 <= i < j < nums.length && reverse(nums[i]) == nums[j]，reverse(x) 将 x 的十进制表示的顺序反转并且去掉前导零。返回镜像对的最小距离。

维护左边的镜像值，枚举右，判断已维护的镜像值中是否存在当前值，取距离的最小值即可。

代码

/**
 * @date 2026-04-17 8:49
 */
public class MinMirrorPairDistance3761 {

    public int minMirrorPairDistance(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        int n = nums.length;
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int num = nums[i];
            if (map.get(num) != null) {
                res = Math.min(res, i - map.get(num));
            }
            int mirror = 0;
            int base = 10;
            while (num > 0) {
                mirror = (num % 10) + mirror * base;
                num /= 10;
            }
            map.put(mirror, i);
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }

}

性能