大家觉得这个怎么样，前面的都是我自己写的，后面实在不知道怎么组织语言了，叫ai帮我写了后面的文字解释，这个能发在leetcode吗，大家看得懂吗 2333.最小差值平方和 题目大致意思 给定两个数组，这两个数组里面的任意数字一次可以 +1 或者 -1 ，数组 1 最多加减 k1 次，数组 2 最多加减 k2 次，然后计算这两个数组同一个 index 位置的差值的平方，将两个数组的所有位置的差值的平方加起来，求它的最小值 大致思路 首先能想到的就是把两个数组里面的数分别拿出来相减然后取绝对值，然后进行排序， k1 和 k2 可以直接加起来当做全部的次数，下面用 k 表示所有的次数；因为绝对值的加减无论是两个数组的那两个进行加减都能达到 -1 的效果，从最高位开始依次开始 -1 ，即慢慢的让数组之间的差值变小，但是存在问题，需要 for 循环多次，算出来时间已经超标了；这里就可以开始优化了，没必要每次只 -1 , 假设 [2,3,6,8,10] 是已经计算好的、进行排序的并且还没经过减少 k 次的两个数组的差值，这里再假设 k=7 首先就是 10-2 得到 [2,3,6,8,8] ，此处 k=2 ，在此处不需要再每个数进行减少，而是分层减少，此时的后两个 8 就可以都同时进行减少，以此减少循环的次数 再就是 8-2 8-2 得到 [2,3,6,6,6] ，此处 k=4 这时 k 还剩 1 ，无论拿哪个 6 进行 -1 就无所谓了，得到的就是 [2,3,5,6,6] 这样的数组 但这时问题又来了，这个问题需要在计算好两个数组差值并进行排序后然后才开始，排序消耗的开销无法避免，而且需要数组一个元素一个元素的遍历过去，整个的时间复杂度会很复杂，像在 [2,3,6,8,8] 时这里的 8 有两个，分层减少也需要进行两次，那如果极限一点 假设存在 [1,2,…,2] ，这里的 2 有 n 个那就需要进行 n 次循环以此进行减小，这时的时间开销就很大了，对于这种情况就需要进行优化了，这里存在的规律就是 相同的数需要进行相同用到减少 ，最后得到的数组需要求整个的平方和，如果是相同的数的话，只需要计算这个数有多少然后乘以这个数的平方就可以，以上面的 [1,2,…,2] 为例， 2 有 n 个， 1 有 1 个，平方和就等于 n22+1 ，也就是说没必要所有的数都进行一次减少，记录这个数出现了多少次，然后同时进行减少就好，如果 k 不够，就只减少部分 最终优化：计数数组（不用排序） 前面已经发现：同一个差值会重复出现，所以没有必要保存并修改每一个元素。 直接记录“每个差值出现了几次” ，就能按差值从大到小批量处理。 例如差值为 [2, 3, 6, 8, 10] ，则 count[10] = 1 、 count[8] = 1 、 count[6] = 1 。当一个 10 减小到 9 时，不必修改原数组，只需将 count[10] 减一、 count[9] 加一。 Java 代码 class Solution { public long minSumSquareDiff(int[] nums1, int[] nums2, int k1, int k2) { // 参考题目条件 int[] count = new int[100001]; long k = (long) k1 + k2; // 计算所有的差值的和的 long total = 0; // 数组有100001个空间，但是进行减少的时候并不需要从100001开始 // 只需要从差值的最大值开始就可以，减少不必要的循环 int max = 0; for (int i = 0; i < nums1.length; i++) { int index = Math.abs(nums1[i] - nums2[i]); count[index]++; total += index; max = Math.max(max,index); } // 如果所有的差值的和比k值小，那就不需要计算了，直接等于0就可以 // 题目也并没有要求要把k用尽，所以减少到0的时候就不需要了 if (k >= total) return 0; // 循环以差值的最大值作为count的起始位置 // 循环条件：数组的位置只要大于0就可以，并且k的次数要大于0 for (int i = max; i > 0 && k > 0; i--) { if (count[i] == 0) continue; int min = (int) Math.min(k, (long) count[i]); count[i] -= min; // 一次只减少一层 count[i - 1] += min; k -= min; } long ans = 0; for (int d = 1; d <= max; d++) { // 相同的数的平方和等于这个数的数量乘以这个数的平方 ans += (long) count[d] d d; } return ans; } } 进一步优化：为什么不直接跳过 count 中为 0 的位置？ 前面的代码采用 count[i - 1] += min ，是每次只下降一个数值等级的简化实现。它已经不会逐个处理相同的元素，但在差值跨度较大时仍会经过中间的空等级。 例如 [10, 6, 2] ，假设 k=5 ： 逐级下降：10→9→8→7→6，用掉 4 次；接着两个 6 中有一个降为 5；最终 [6,5,2] 。 直接跳层：找到 10 的下一处非零计数位置 6。计算 need=(10-6)1=4 ， k=5 足够，一次把计数从 10 转移到 6。剩下 1 次再处理两个 6，结果一样。 不能无条件跳到下一层。 假设差值 [10,10,10,6] ， k=5 ，从 10 到 6 需要 (10-6)3=12 次，但只有 5 次。此时： q=k/count[10]=5/3=1 ：三个 10 都能下降 1，变成三个 9。 r=k%count[10]=5%3=2 ：另外还能让两个 9 各下降 1。 最终差值是 [8,8,9,6] ，不能直接变成三个 6。 直接跳层的关键代码 int next = d - 1; while (next > 0 && count[next] == 0) { next--; // 跳过没有差值的等级 } long amount = count[d]; long need = (long) (d - next) amount; 这里 next 是下一个存在差值的位置；若一直没有找到，则以 0 为目标。 amount 是当前最大差值的数量。要让这一批数全部从 d 降到 next ，需要 need 次操作。 如果 k >= need ，可以把整批计数转移到 next ，并与原本就位于 next 的计数合并。否则，使用商 q=k/amount 和余数 r=k%amount ，分别把 amount-r 个放到 d-q ，把 r 个放到 d-q-1 ，操作次数恰好用完。 优化后的完整 Java 代码 class Solution { public long minSumSquareDiff(int[] nums1, int[] nums2, int k1, int k2) { int[] count = new int[100001]; long k = (long) k1 + k2; long total = 0; int max = 0; // 统计每个差值出现多少次 for (int i = 0; i < nums1.length; i++) { int index = Math.abs(nums1[i] - nums2[i]); count[index]++; total += index; max = Math.max(max, index); } // 操作次数足够消除全部差值 if (k >= total) return 0; int i = max; while (i > 0 && k > 0) { if (count[i] == 0) { i--; continue; } // 找到下一个有计数的位置；最少可以降到 0 int next = i - 1; while (next > 0 && count[next] == 0) { next--; } long num = count[i]; long need = (long) (i - next) num; if (k >= need) { // 整批从 i 降到 next count[next] += count[i]; count[i] = 0; k -= need; i = next; } else { // 不够到达 next：平均下降 q 层，余下 r 次 int q = (int) (k / num); int r = (int) (k % num); count[i] = 0; count[i - q] += (int) num - r; count[i - q - 1] += r; k = 0; } } long ans = 0; for (int i = 1; i <= max; i++) { ans += (long) count[i] i i; } return ans; } } 1 个帖子 - 1 位参与者 阅读完整话题

  • 情报分类：技术学习与提效
  • 分类依据：内容涉及技术、AI、软件工具或工程实践
  • 信息来源：服务器 / LINUX DO - 最新话题
  • 发布时间：2026/10/10 17:13:40