企业官网建设流程全解析

LeetCode-Go 题解 1300. Sum of Mutated Array Closest to Target：二分搜索逼近目标和的“截断数组”问题

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

本篇以 LeetCode-Go 仓库中 1300. Sum of Mutated Array Closest to Target 题解文档 为骨架，结合仓库内的 Go 实现源码 与 单元测试，系统讲解如何利用二分搜索在单调变化的“截断和”上求解最优变异阈值 value，覆盖题目约束、二分单调性论证、平局处理、边界特判与复杂度分析。读完本文，你将掌握这类“截断求和 + 最接近目标”问题的通用二分建模方法，并能直接复现仓库中的解法与测试流程。

题目

Given an integer arrayarrand a target valuetarget, return the integervaluesuch that when we change all the integers larger thanvaluein the given array to be equal tovalue, the sum of the array gets as close as possible (in absolute difference) totarget.

In case of a tie, return the minimum such integer.

Notice that the answer is not necessarily a number fromarr.

翻译成中文即：给你一个整数数组arr和一个目标值target，请你返回一个整数value，使得将数组中所有大于value的值变成value后，数组的和最接近target（“最接近”表示两者之差的绝对值最小）。如果有多种使得和“最接近 target”的方案，请你返回这些整数中的最小值。请注意，答案不一定是arr中的数字。

示例

Example 1

Input: arr = [4,9,3], target = 10 Output: 3 Explanation: When using 3 arr converts to [3, 3, 3] which sums 9 and that's the optimal answer.

当 value = 3 时，数组[4, 9, 3]中大于 3 的元素全部截断为 3，得到[3, 3, 3]，和为 9，与 target = 10 的绝对差为 1，是所有候选 value 中最优的。

Example 2

Input: arr = [2,3,5], target = 10 Output: 5

当 value = 5 时，数组中没有任何元素大于 5，数组保持[2, 3, 5]不变，和为 10，恰好等于 target。

Example 3

Input: arr = [60864,25176,27249,21296,20204], target = 56803 Output: 11361

约束条件

• 1 <= arr.length <= 10^4
• 1 <= arr[i], target <= 10^5

题目分析：一个带“截断”的求和问题

把问题翻译成更直观的模型：我们选择一个阈值value（不要求它来自arr），然后对数组做一次“截断”操作：

newArr[i] = min(arr[i], value)

即每个元素取arr[i]与value的较小者。目标是在整数域[0, +∞)上寻找一个value，使截断后数组的总和S(value) = Σ min(arr[i], value)与target的绝对差最小；若存在多个最优值，取其中最小的。

这道题有两个值得注意的特性：

1. 答案不一定是arr中的元素。例如 Example 3 中输出 11361 并不在输入数组里，因此不能只枚举数组中的元素，必须面向整个整数取值域求解。
2. 平局取最小。当多个value使|S(value) - target|相等时，必须返回最小的那个value，这直接决定了最终比较逻辑的写法。

解题思路：基于单调性的二分搜索

原文档明确给出了本题的核心解法：二分搜索。为什么要用二分？关键在于S(value)关于value具有单调不减的性质：

• 当value增大时，min(arr[i], value)只会不变或变大（小于等于value的元素保持不变，大于value的元素随阈值上移而变大），因此S(value)单调不减；
• 当value足够大（不小于数组最大值）时，S(value)达到上界sum(arr)并保持恒定。

单调性使得“寻找使S(value)最接近target的value”可以转化为在数值轴上二分定位。仓库解法将搜索区间设为[0, 100000]，上界 100000 直接来自约束arr[i] <= 10^5——阈值超过数组最大值后结果不再变化，因此不必搜索更大的范围。

原文档还特别提示了一个二分中的“陷阱”：由于数组中每个数与mid的差距各不相同，每次调整mid时可能出现“mid选小了，距离target反而更大；mid选大了，距离target反而更小”的非单调现象。换句话说，|S(mid) - target|本身不是单调函数，单纯按差值大小收缩区间是不可靠的。解决办法是：二分时只看S(mid)与target的大小关系定位分界点，最终把阈值线上下可能的值都取出来比较一次。

源码实现逐行解析

仓库中的 完整实现 由三个函数组成，与题解文档中的代码完全一致：

func findBestValue(arr []int, target int) int { low, high := 0, 100000 for low < high { mid := low + (high-low)>>1 if calculateSum(arr, mid) < target { low = mid + 1 } else { high = mid } } if high == 100000 { res := 0 for _, num := range arr { if res < num { res = num } } return res } // 比较阈值线分别定在 left - 1 和 left 的时候与 target 的接近程度 sum1, sum2 := calculateSum(arr, low-1), calculateSum(arr, low) if target-sum1 <= sum2-target { return low - 1 } return low } func calculateSum(arr []int, mid int) int { sum := 0 for _, num := range arr { sum += min(num, mid) } return sum } func min(a int, b int) int { if a > b { return b } return a }

1. 辅助函数calculateSum：截断求和的核心

func calculateSum(arr []int, mid int) int { sum := 0 for _, num := range arr { sum += min(num, mid) } return sum }

该函数在给定阈值mid时，对每个元素执行min(num, mid)并累加，即前面推导的S(mid) = Σ min(arr[i], mid)。它完整实现了题目中的“将所有大于 value 的值变成 value”这一截断语义，是整个二分循环中被反复调用的代价函数。每次调用时间复杂度为O(n)。

min是仓库内手写的两数取小函数，等价于标准库的min内建函数（Go 1.21+），仓库基于 Go 1.19（见 go.mod），因此在源码中显式实现以保证兼容性。

2. 主函数findBestValue：二分定位 + 邻值决胜

low, high := 0, 100000 for low < high { mid := low + (high-low)>>1 if calculateSum(arr, mid) < target { low = mid + 1 } else { high = mid } }

这段是左闭右开二分模板（low取得到、high取不到）：

• 当S(mid) < target时，说明阈值偏小、截断后总和不够，最优值只可能在右侧，令low = mid + 1；
• 当S(mid) >= target时，令high = mid，不断向“首个使S(value) >= target的 value”收敛。

循环结束时low == high，这个值就是使截断和首次达到 target 的最小阈值，记为low。这里的依据是S(value)的单调性：low - 1一定满足S(low-1) < target，low满足S(low) >= target，因此全局最接近 target 的阈值只可能出现在low - 1与low这两个邻值之间，这就是原文档所说的“把 value 上下方可能的值都拿出来比较一下”。

3. 边界特判：所有元素都被“截断到顶”

if high == 100000 { res := 0 for _, num := range arr { if res < num { res = num } } return res }

若循环结束后high仍然等于初始上界 100000，说明即使阈值取到约束最大值10^5，S(100000)依然小于target——即整个数组之和都达不到 target。此时阈值继续增大也不会改变截断结果（所有元素都小于等于阈值，数组保持不变），最接近 target 的 value 就是能保持数组原状的最小值，即数组的最大元素。这里通过一次线性扫描求出max(arr)返回。

4. 邻值决胜：平局取最小值

sum1, sum2 := calculateSum(arr, low-1), calculateSum(arr, low) if target-sum1 <= sum2-target { return low - 1 } return low

• sum1 = S(low-1) < target，与 target 的差距为target - sum1；
• sum2 = S(low) >= target，与 target 的差距为sum2 - target。

比较两者：

• 若target - sum1 <= sum2 - target，即左侧阈值更接近（或平局），返回较小的low - 1，正好满足题目“平局返回最小值”的要求；
• 否则返回low。

这段代码是原文档解题思路中“2 个限制条件”的落地体现：既保证绝对差最小，又保证平局时输出最小 value。

复杂度分析

设数组长度为n，二分取值域为[0, 100000]（常数上界C = 10^5）：

• 时间复杂度：O(n · log C)。二分迭代约log₂(10^5) ≈ 17轮，每轮调用calculateSum需要O(n)遍历，此外至多还有两次O(n)的邻值求和与一次O(n)的最大值扫描，均被主项覆盖。
• 空间复杂度：O(1)，全程仅使用若干整型变量，无额外数据结构。

对于约束上限n = 10^4来说，约1.7 × 10^5次元素访问的规模可以在毫秒级内完成，完全满足 LeetCode 的时间限制。

测试用例与仓库验证

仓库为该题提供了 单元测试文件，以表驱动方式覆盖了以下用例：

第 3 个用例是仓库作者补充的边界场景：当target = 11时，value = 5对应和 10，value = 6对应和 12，两者距 target 均为 1 形成平局，按题意应返回较小值 5——正是第 4 步邻值决胜逻辑要处理的典型输入。测试运行时会逐条打印输入输出便于比对：

fmt.Printf("【input】:%v 【output】:%v\n", p, findBestValue(p.arr, p.target))

若想在本地复现，可在仓库根目录执行单题测试：

go test -v -run Test_Problem1300 ./leetcode/1300.Sum-of-Mutated-Array-Closest-to-Target/

仓库的 gotest.sh 还提供了全量测试脚本，会对./leetcode/...下所有题目执行go test -covermode=atomic -coverprofile=coverage.txt，以生成统一格式的覆盖率文件；本题的源码与测试同样纳入该全量流程，保证每个题解都附带可运行的验证。

另外，该题在仓库网站目录下还有一份同内容文档 website/content/ChapterFour/1300~1399/1300.Sum-of-Mutated-Array-Closest-to-Target.md，与本文所述题解文档保持一致，供在线阅读与检索使用。

小结

LeetCode 1300 的仓库题解展示了二分搜索处理“非单调差值、单调原函数”问题时的正确姿势：

1. 识别单调量：S(value) = Σ min(arr[i], value)随value单调不减，是二分合法性的根基；
2. 二分定位分界点：用S(mid)与target的大小关系收缩区间，找到首次越过 target 的阈值low；
3. 邻值决胜：全局最优只可能在low - 1与low之间，分别计算距离，平局取小；
4. 边界特判：阈值到顶仍达不到 target 时，返回数组最大值。

这种“截断求和 + 二分查找分界点 + 邻值比较”的建模方法可以迁移到一系列“阈值截断”类问题中，例如资源分配、区间裁剪等场景，是值得反复演练的二分经典套路。

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