LeetCode 每日一题笔记

0. 前言

• 日期：2026.04.23
• 题目：2615. 等值距离和
• 难度：中等
• 标签：数组、哈希表、前缀和

1. 题目理解

问题描述： 给定一个下标从 0 开始的整数数组 nums，返回一个与 nums 长度相同的数组 arr。对于每个 i，arr[i] 等于所有满足 nums[j] == nums[i] 且 j != i 的下标 j 与 i 的距离 |i-j| 之和；如果不存在这样的 j，则 arr[i] 为 0。

示例： 输入：nums = [1,3,1,1,2] 输出：[5,0,3,4,0] 解释：

• i=0，nums[0]=1，同值下标为 0,2,3，arr[0] = |0-2| + |0-3| = 2+3=5
• i=1，nums[1]=3，无其他同值下标，arr[1]=0
• i=2，nums[2]=1，同值下标为 0,2,3，arr[2] = |2-0| + |2-3| = 2+1=3
• i=3，nums[3]=1，同值下标为 0,2,3，arr[3] = |3-0| + |3-2| = 3+1=4
• i=4，nums[4]=2，无其他同值下标，arr[4]=0

2. 解题思路

核心观察

1. 暴力解法直接对每个 i 遍历所有 j 计算距离和，时间复杂度为 $O(n^2)$，会超时。
2. 对于相同数值的所有下标，距离和可通过前缀和优化，避免重复计算。
3. 对同一数值的下标列表，利用前缀和可将每个下标的距离和计算时间降为 $O(1)$。

算法步骤

1. 分组存储：用哈希表将数组中相同数值的下标存储为列表。
2. 前缀和预处理：对每个数值的下标列表，计算前缀和数组，用于快速计算左右两侧的距离和。
3. 计算距离和：对每个下标，利用前缀和分别计算左侧和右侧的距离和，相加得到最终结果。

3. 代码实现

package lc2615;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class lc3600_lc3699.lc3660.Solution {
    public long[] distance(int[] nums) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            map.computeIfAbsent(nums[i], k -> new ArrayList<>()).add(i);
        }
        long[] ans = new long[n];
        for (List<Integer> list : map.values()) {
            int m = list.size();
            long[] prefix = new long[m + 1];
            for (int i = 0; i < m; i++) {
                prefix[i + 1] = prefix[i] + list.get(i);
            }
            for (int k = 0; k < m; k++) {
                long idx = list.get(k);
                long left = idx * k - prefix[k];
                long right = (prefix[m] - prefix[k + 1]) - idx * (m - k - 1);
                ans[list.get(k)] = left + right;
            }
        }
        return ans;
    }
}

4. 代码优化说明

1. 哈希表分组：通过一次遍历将相同数值的下标分组，时间复杂度 $O(n)$。
2. 前缀和优化：对每个分组的下标列表计算前缀和，使得每个下标的距离和计算为 $O(1)$。
3. 左右距离分离计算：将总距离拆分为左侧距离和右侧距离，利用前缀和分别计算，避免重复遍历。
4. 避免溢出：使用 long 类型存储前缀和与结果，防止整数溢出。

5. 复杂度分析

• 时间复杂度：$O(n)$
  • 分组遍历：$O(n)$；
  • 每个分组的前缀和计算与距离和计算均为线性时间，整体遍历所有元素一次，总时间为 $O(n)$。
• 空间复杂度：$O(n)$
  • 哈希表存储所有下标，空间为 $O(n)$；
  • 前缀和数组空间为分组大小之和，不超过 $O(n)$。

6. 总结

• 本题核心是利用哈希表分组+前缀和将暴力解法的 $O(n^2)$ 优化为 $O(n)$。
• 关键在于理解同一数值的下标列表可通过前缀和快速计算距离和，无需重复遍历。
• 前缀和的使用将每个下标的距离和计算从线性时间降为常数时间，是优化的核心。
• 需注意使用 long 类型避免距离和计算时的整数溢出问题。