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

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 1Input: arr [4,9,3], target 10 Output: 3 Explanation: When using 3 arr converts to [3, 3, 3] which sums 9 and thats the optimal answer.当 value 3 时数组[4, 9, 3]中大于 3 的元素全部截断为 3得到[3, 3, 3]和为 9与 target 10 的绝对差为 1是所有候选 value 中最优的。Example 2Input: arr [2,3,5], target 10 Output: 5当 value 5 时数组中没有任何元素大于 5数组保持[2, 3, 5]不变和为 10恰好等于 target。Example 3Input: arr [60864,25176,27249,21296,20204], target 56803 Output: 11361约束条件1 arr.length 10^41 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的绝对差最小若存在多个最优值取其中最小的。这道题有两个值得注意的特性答案不一定是arr中的元素。例如 Example 3 中输出 11361 并不在输入数组里因此不能只枚举数组中的元素必须面向整个整数取值域求解。平局取最小。当多个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) targetlow满足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^5S(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 lowsum1 S(low-1) target与 target 的差距为target - sum1sum2 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 的时间限制。测试用例与仓库验证仓库为该题提供了 单元测试文件以表驱动方式覆盖了以下用例输入 arrtarget期望输出覆盖点[4, 9, 3]103官方示例截断后[3,3,3]和为 9距离最近[2, 3, 5]105官方示例数组和恰好等于 target[2, 3, 5]115仓库补充用例平局/紧邻场景[60864, 25176, 27249, 21296, 20204]5680311361官方示例答案不在 arr 中第 3 个用例是仓库作者补充的边界场景当target 11时value 5对应和 10value 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 -covermodeatomic -coverprofilecoverage.txt以生成统一格式的覆盖率文件本题的源码与测试同样纳入该全量流程保证每个题解都附带可运行的验证。另外该题在仓库网站目录下还有一份同内容文档 website/content/ChapterFour/1300~1399/1300.Sum-of-Mutated-Array-Closest-to-Target.md与本文所述题解文档保持一致供在线阅读与检索使用。小结LeetCode 1300 的仓库题解展示了二分搜索处理“非单调差值、单调原函数”问题时的正确姿势识别单调量S(value) Σ min(arr[i], value)随value单调不减是二分合法性的根基二分定位分界点用S(mid)与target的大小关系收缩区间找到首次越过 target 的阈值low邻值决胜全局最优只可能在low - 1与low之间分别计算距离平局取小边界特判阈值到顶仍达不到 target 时返回数组最大值。这种“截断求和 二分查找分界点 邻值比较”的建模方法可以迁移到一系列“阈值截断”类问题中例如资源分配、区间裁剪等场景是值得反复演练的二分经典套路。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考