LeetCode-Go 题解精读：1818. Minimum Absolute Sum Difference（最小绝对差值和）

LeetCode-Go 题解精读：1818. Minimum Absolute Sum Difference（最小绝对差值和）

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

导读

本文围绕 LeetCode 第 1818 题「Minimum Absolute Sum Difference（最小绝对差值和）」展开，完整解析题目定义、收益模型推导与 Go 语言实现。题目要求在只允许替换nums1中至多一个元素的条件下，最小化两个数组对应位置绝对差的总和，属于「枚举 + 数学变换」类型的经典问题。读完本文，你将掌握：绝对差值和问题的数学建模方法、将"最小化总和"转化为"最大化替换收益 Δ"的推导过程，以及本仓库 LeetCode-Go 中该题解的具体实现、剪枝细节与测试用例验证方式。

题目描述

给定两个正整数数组nums1和nums2，长度均为n。数组nums1与nums2的绝对差值和定义为：对每个下标0 <= i < n，计算|nums1[i] - nums2[i]|并求和。

你可以选用nums1中的任意一个元素，去替换nums1中的至多一个元素，以最小化绝对差值和。在完成替换之后，返回最小的绝对差值和。由于答案可能很大，需要对10^9 + 7取余后返回。

其中|x|的定义为：当x >= 0时取x，当x < 0时取-x。

示例与预期输出

示例 1：

输入：nums1 = [1,7,5], nums2 = [2,3,5] 输出：3 解释：存在两种最优替换方案： - 将第二个元素替换为第一个：[1,7,5] => [1,1,5] - 将第二个元素替换为第三个：[1,7,5] => [1,5,5] 两种方案都能得到绝对差值和 |1-2| + (|1-3| 或 |5-3|) + |5-5| = 3

示例 2：

输入：nums1 = [2,4,6,8,10], nums2 = [2,4,6,8,10] 输出：0 解释：nums1 与 nums2 完全相等，无需任何替换，绝对差值和即为 0。

示例 3：

输入：nums1 = [1,10,4,4,2,7], nums2 = [9,3,5,1,7,4] 输出：20 解释：将第一个元素替换为第二个：[1,10,4,4,2,7] => [10,10,4,4,2,7] 绝对差值和为 |10-9| + |10-3| + |4-5| + |4-1| + |2-7| + |7-4| = 20

约束条件

• n == nums1.length
• n == nums2.length
• 1 <= n <= 10^5
• 1 <= nums1[i], nums2[i] <= 10^5

从约束可以看出：n最大可达10^5，这意味着数组规模较大；而元素值域为1到10^5，任意两个元素的差的绝对值最大为99999，这一数值边界与题解实现中的哨兵值设计直接相关，下文会展开说明。

解题思路：从数学建模到收益最大化

第一步：定义不替换时的绝对差值和

如果不改变任何元素，绝对差值和为：

$$\sum_{i=0}^{n-1} \left | nums1[i] - nums2[i] \right |$$

第二步：建立"替换一次"的收益模型

假设将nums1[i]替换为nums1[j]（j可以是任意下标，包括i本身），那么位置i上的差值会从|nums1[i] - nums2[i]|变为|nums1[j] - nums2[i]|，其余位置不受影响。替换后的总差值和为：

$$\sum_{i=0}^{n-1} \left | nums1[i] - nums2[i] \right | - \left( \left | nums1[i] - nums2[i] \right | - \left | nums1[j] - nums2[i] \right | \right)$$

记

$$\Delta = \left | nums1[i] - nums2[i] \right | - \left | nums1[j] - nums2[i] \right |$$

则替换后的绝对差值和 = 原始总和 − Δ。

第三步：最小化总和等价于最大化 Δ

题目要求返回最小的绝对差值和，因此等价于在所有可能的替换方案中求 Δ 的最大值。其中 Δ 的含义非常直观：用nums1[j]替换nums1[i]后，位置i上的差值减少了多少。Δ 越大，总和的削减越多。

由此，暴力解法便呼之欲出：枚举每一个可能被替换的位置i，再枚举nums1中的每一个候选替换元素nums1[j]，计算对应的 Δ，最终取最大值maxDiff，答案即为：

$$\text{原始总和} - \max \Delta$$

源码实现精读

本仓库 LeetCode-Go 中该题的完整实现位于 1818. Minimum Absolute Sum Difference.go，核心代码如下：

func minAbsoluteSumDiff(nums1 []int, nums2 []int) int { diff := 0 maxDiff := 0 for i, n2 := range nums2 { d := abs(nums1[i] - n2) diff += d if maxDiff < d { t := 100001 for _, n1 := range nums1 { maxDiff = max(maxDiff, d-min(t, abs(n1-n2))) } } } return (diff - maxDiff) % (1e9 + 7) } func max(a, b int) int { if a > b { return a } return b } func abs(a int) int { if a > 0 { return a } return -a } func min(a, b int) int { if a > b { return b } return a }

主循环：统计原始差值总和

for i, n2 := range nums2 { d := abs(nums1[i] - n2) diff += d ... }

第一重循环遍历所有下标i，以nums2为基准计算d = |nums1[i] - nums2[i]|，并累加到diff中。这一过程同时完成了两件事：记录原始绝对差值和diff，并为后续的收益计算提供每个位置的原始差值d。

内层枚举与关键剪枝

if maxDiff < d { t := 100001 for _, n1 := range nums1 { maxDiff = max(maxDiff, d-min(t, abs(n1-n2))) } }

内层循环枚举所有候选替换元素n1：若用n1替换nums1[i]，位置i的新差值为abs(n1-n2)，收益为d - abs(n1-n2)，取历史最大值即可得到全局最大收益maxDiff。

这里有一个非常关键的剪枝条件：if maxDiff < d。为什么可以这样剪枝？因为收益的数学上界是d（当新差值abs(n1-n2)取到最小值0，即候选元素与nums2[i]完全相等时，收益才达到上限d）。因此，若当前位置的原始差值d已经不大于当前已知的最大收益maxDiff，那么即使在该位置上做到完美替换，收益也不可能超过maxDiff，内层枚举可以直接跳过。从实现看可以推断，这个剪枝在数据"差值递增、收益越算越大"的场景下能把内层循环压缩掉大部分，是这段暴力代码在多数测试数据下仍能较快通过的关键。

哨兵值 100001 的含义

内层循环中的t := 100001是一个值得注意的细节。由于题目约束1 <= nums1[i], nums2[i] <= 10^5，任意两个元素的差的绝对值最大为99999，恒小于100001，因此min(t, abs(n1-n2))在合法输入范围内永远等于abs(n1-n2)，t实质上充当了"正无穷"哨兵的角色，等价于直接取abs(n1-n2)。从实现结构看，可以推断作者用min统一处理候选差值的取值逻辑，哨兵值保证了该式在题目约束内不会引入额外分支。

需要说明的是，仓库测试文件 1818. Minimum Absolute Sum Difference_test.go 中额外包含了一组超出题目约束值域的用例nums1 = [1, 200000]、nums2 = [200000, 1]（期望输出199999），该用例恰好覆盖了大数值差值的极端场景。

结果取模

return (diff - maxDiff) % (1e9 + 7)

最终答案即原始总和 - 最大收益。由于maxDiff <= diff恒成立（收益不会超过所有原始差值之和，且d <= diff），diff - maxDiff非负，直接对10^9 + 7取模即可，与题目要求一致。代码中1e9 + 7作为无类型浮点常量在整数上下文中会被精确转换为1000000007，语法合法。

辅助函数

max、min、abs三个辅助函数均为简单的分支判断实现，没有任何依赖外部库，代码风格与仓库中其他题解保持一致。

复杂度分析

• 时间复杂度：最坏情况下为O(n²)。当每个位置的新差值d都大于当前maxDiff（例如差值单调递增）时，每个下标都会触发完整的内层枚举；当maxDiff较早达到较大值后，后续位置大多被剪枝跳过，实际运行远优于最坏情况。
• 空间复杂度：O(1)，仅使用常数个额外变量，未引入任何辅助数组或哈希表。

测试用例验证

仓库为该题编写了结构化的表格驱动测试，见 1818. Minimum Absolute Sum Difference_test.go，测试框架与其他题解一致：定义para1818（输入参数）与ans1818（期望答案）结构体，通过Test_Problem1818循环断言minAbsoluteSumDiff的输出与期望值一致，不匹配时调用t.Fatalf报错。

测试共覆盖 4 组用例：

运行与验证方式

该题解位于仓库leetcode/1818.Minimum-Absolute-Sum-Difference/目录下，与仓库中所有题解一样按题号.题名组织。仓库根目录的 gotest.sh 提供了统一跑测试与覆盖率的方式：

go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...

对单题验证，可在对应目录下执行：

go test -v -run Test_Problem1818 ./leetcode/1818.Minimum-Absolute-Sum-Difference/

仓库基于 Go 1.19（见 go.mod），运行前需确保本地 Go 环境版本不低于该要求。

进阶思考：从 O(n²) 到 O(n log n)

在n <= 10^5的约束下，暴力枚举的最坏复杂度为O(n²)，当数据构造为最坏形态时仍可能偏慢。一个在算法层面常见（并非本仓库实现）的优化方向是：排序 + 二分查找。

由于收益 Δ 只关心"与nums2[i]最接近的nums1元素"，可以将nums1排序后，对每个nums2[i]使用二分查找定位其前驱与后继，从中选出使|nums1[j] - nums2[i]|最小的候选，从而把内层枚举从O(n)降到O(log n)，整体复杂度优化至O(n log n)。这一思路是同类"最小绝对差"问题的通用套路，读者可以在此基础上自行验证：本仓库提供的O(n²) + 剪枝实现正确性优先、代码直观，是理解题目收益模型的最佳起点；而二分优化版本则在极限数据下具备更强的性能保障。

小结

本题的核心价值在于一步漂亮的数学转化：把"替换至多一个元素使总和最小"建模为"计算每个位置的替换收益 Δ 并求最大值"，从而将问题化归为一次遍历统计 + 一次候选枚举。结合 LeetCode-Go 仓库的源码与测试，读者可以完整掌握该题从题意、推导、实现到验证的全链路，同时体会剪枝条件与哨兵值等工程细节在竞赛题解中的实际作用。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go