- 正确答案：对于数组中每个元素 nums[i]，计算所有满足 nums[j] == nums[i] 且 j ≠ i 的 |i - j| 之和，最终返回一个长度为 n 的结果数组 ans，其中 ans[i] = Σ_{j: nums[j]==nums[i], j≠i} |i - j|。该问题可在 O(n) 时间复杂度内解决（单次遍历预处理 + 单次遍历计算），核心是利用「同值元素下标序列」的前缀和性质，对每个数值分组后，用数学公式 O(1) 计算每个位置的贡献。 - 解答思路： 1. 第一步：按数值分组，收集所有相同元素的下标，例如 nums = [1,3,1,1,2] → map{1:[0,2,3], 3:[1], 2:[4]}。 2. 第二步：对每组下标列表 idxs（长度为 m），计算每个 idxs[k] 对应的距离和。暴力法是 O(m²)，但可优化：设前缀和数组 pre[m+1]，pre[0]=0, pre[i]=idxs[0]+...+idxs[i-1]；则对位置 k（下标 idxs[k]），其左侧有 k 个元素（下标 < idxs[k]），右侧有 m−k−1 个元素（下标 > idxs[k]）。距离和 = (k * idxs[k] − sum_left) + (sum_right − (m−k−1) * idxs[k])，其中 sum_left = pre[k]，sum_right = pre[m] − pre[k+1]。 3. 第三步：将每组计算结果填入 ans 对应原始下标位置。整体时间复杂度 O(n)，空间复杂度 O(n)。 - 深度知识讲解：本题本质考察「离线查询 + 分组 + 前缀和优化 + 数学推导能力」，是典型的“同值元素距离和”模型（LeetCode 1685 / 1718 / 2121 等变种）。关键底层原理在于：绝对值求和 Σ|p − x_i| 在有序点集 {x_i} 上关于 p 的函数是分段线性凸函数，最小值在中位数处取得；而当 p 固定为某个 x_k 时，可拆分为左右两部分线性求和。进一步抽象，这是「一维曼哈顿距离聚合」的经典场景，其高效解法依赖两个前提：（1）数据天然可分组（哈希分桶），（2）组内坐标有序（插入时排序或遍历时自然有序）。若不排序，需额外 O(m log m)；但因下标遍历顺序即插入顺序，我们可在建 map 时直接 push_back，后续对每组 sort —— 实际中更优做法是：一次扫描建立 map>，再对每个 vector 排序（总排序代价仍 O(n log n_w)，n_w 为某值出现频次，最坏 O(n log n)）。但本题可通过两次扫描避免显式排序：第一次记录首次/末次出现位置及频次，第二次用「贡献法」—— 更高阶技巧是「两次线性扫描法」：先左到右扫，维护每个值的已见下标和数量，计算左半贡献；再右到左扫，计算右半贡献。但该方法需维护 per-value 的 running sum 和 count，实现稍复杂。因此标准最优解仍是分组 + 排序 + 前缀和。底层数据结构选择：unordered_map> 是必须的，vector 支持 O(1) 尾插和随机访问；前缀和用 int64_t 防止溢出（因距离和可能达 1e10 量级）；注意 C++ 中 vector::at() 边界检查开销，生产代码可用 [] 加 assert。实现原理细节：假设 idxs = [i0,i1,...,i_{m-1}] 严格递增，则对 k ∈ [0,m−1]： left_sum = i0 + i1 + ... + i_{k−1} = pre[k] right_sum = i_{k+1} + ... + i_{m−1} = pre[m] − pre[k+1] ans[idxs[k]] = k * idxs[k] − left_sum + right_sum − (m−1−k) * idxs[k] = (2k − m + 1) * idxs[k] + (right_sum − left_sum) 这一公式可进一步简化为：= idxs[k] * (2k − m + 1) + (pre[m] − pre[k+1] − pre[k]) 该推导暴露了算法本质：每个位置的贡献由其在有序下标中的秩（k）和全局前缀和决定，是典型的「序统计 + 累加器」模式，与树状数组/线段树的区间求和思想同源，但此处因查询固定且批量，前缀和更轻量。 - 伪代码（C++ 风格，含注释）： vector getDistanceSum(vector& nums) { int n = nums.size(); unordered_map> groups; // Step 1: 分组，记录每个值的所有下标 for (int i = 0; i < n; ++i) { groups[nums[i]].push_back(i); } vector ans(n, 0); // Step 2: 对每组处理 for (auto& [val, idxs] : groups) { int m = idxs.size(); if (m == 1) continue; // 单个元素距离和为0 sort(idxs.begin(), idxs.end()); // 保证有序（实际插入有序，但保险起见） // 构建前缀和 pre[0..m], pre[i] = sum of idxs[0] to idxs[i-1] vector pre(m + 1, 0); for (int i = 0; i < m; ++i) { pre[i + 1] = pre[i] + idxs[i]; } // 对每个下标位置 k，计算其在组内的距离和 for (int k = 0; k < m; ++k) { long long left_sum = pre[k]; // idxs[0]..idxs[k-1] long long right_sum = pre[m] - pre[k + 1]; // idxs[k+1]..idxs[m-1] long long dist_sum = 1LL * k * idxs[k] - left_sum + right_sum - 1LL * (m - 1 - k) * idxs[k]; ans[idxs[k]] = dist_sum; } } return ans; } - 扩展知识： 1. 若题目升级为「动态数组，支持单点修改 + 查询某位置距离和」，则需用带权平衡BST或线段树维护每个值的下标集合，支持插入/删除/O(log m) 查询秩和区间和。 2. 若扩展到二维：给定点集 {(x_i,y_i)}，求每个点到同色点的曼哈顿距离和，则需分别对 x 和 y 坐标独立分组+前缀和，再合并（因 |x_i−x_j|+|y_i−y_j| 可分离）。 3. 相关工业应用：推荐系统中计算用户行为序列中某次点击与历史同类行为的时间间隔和；数据库索引优化中评估等值查询的物理局部性代价。 4. 常见错误：未用 long long 导致整型溢出；未排序 idxs 导致前缀和错位；混淆下标 k 与原始数组下标 idxs[k]；边界处理错误（如 k=0 时 left_sum=0，k=m−1 时 right_sum=0）。

4.23 百度暑期实习 大数据存储研发 一面

全站热榜

创作者周榜

4.23 百度暑期实习大数据存储研发一面