LeetCode 补充题 8. 计算数组的小和
目录
题目描述
✅ 补充题 8. 计算数组的小和
题意分析
「小和」的定义是：对数组里的每一个元素，把它左边所有严格小于它的数加起来，再把所有元素的这份和累加。例如
[1, 3, 4, 2, 5]，元素 1 左边没有数贡献 0，元素 3 左边只有 1 比它小贡献 1，元素 4 左边有 1 和 3 贡献 4，元素 2 左边只有 1 贡献 1，元素 5 左边 1、3、4、2 全比它小贡献 10，总小和是 16。定义里有两个必须抠死的字眼。一是「左边」，说明这是一个有序对的统计：只有下标小的贡献给下标大的，方向不能反。二是「严格小于」，相等不算，所以
[1, 1]的小和是 0 而不是 1——这个细节会直接决定代码里比较符的写法，也是本题最常见的失分点。换个角度看，小和等于对所有满足
i < j且nums[i] < nums[j]的下标对，把nums[i]加起来。也就是说每个元素被计入的次数，等于它右边比它大的元素个数。这两种视角完全等价，但后者更容易发现优化空间：我们真正需要的从来不是「谁比谁小」的明细，而是某个值被计入了多少次这个计数，这就给了批量处理的余地。本题是补充题，没有官方数据范围，面试里通常按 $n \le 10^5$、元素为 32 位整数来准备。据此可以定下两件事：$O(n^2)$ 的双重循环在这个规模下是 $10^{10}$ 次操作，必然超时；答案在最坏情况（数组升序且元素都取 $10^9$）约为 $10^9 \times \frac{n(n-1)}{2} \approx 5 \times 10^{18}$，远远越过 int 上界但仍落在 64 位整数范围内，所以累加变量必须用
long/int64，而 64 位已经够用。边界情形：空数组和只有一个元素的数组答案都是 0；元素可以为负数，负数同样按大小关系参与贡献，不能想当然地跳过；全部元素相等时答案是 0；数组已经升序时贡献最大，是检验溢出的最好用例；数组降序时答案是 0。
解法：归并排序统计跨区间贡献
核心思路
小和可以换一个等价视角：对每个位置
i，nums[i]会被计入“右侧比它大的元素个数”次。暴力逐对统计需要 $O(n^2)$；若左右两段已经有序，就能在归并时一次结算一批贡献。分治后，小和由三部分组成：左半内部、右半内部、左半到右半的跨区间贡献。前两部分递归计算，第三部分在合并两个有序段时计算。
合并时若
nums[i] < nums[j]，右半的nums[j..right]都严格大于nums[i]，所以一次累加
nums[i] * (right - j + 1)。若两者相等，必须先取右侧且不统计，因为题目要求严格小于。每次合并后都要把有序结果写回原数组，保证上一层继续满足“两侧有序”的前提。递归返回值就是两侧答案与本层跨区间贡献之和。
解题步骤
- 申请一个与原数组等长的临时数组，整棵递归树复用。
- 将区间
[left, right]分成两半，递归得到两侧小和并将两侧排好序。- 用双指针合并。左值小于右值时，批量累加它对右侧剩余元素的贡献。
- 某一侧耗尽后复制另一侧剩余元素，再把临时数组写回原区间。
- 所有贡献使用
long/int64累加，乘法也必须先提升到 64 位。以
[1, 3, 4, 2, 5]为例，顶层合并[1,3,4]与[2,5]时，跨区间贡献为1*2 + 3*1 + 4*1 = 9；加上左右内部的 5 和 2，得到总小和 16。
代码实现
class Solution {
public long smallSum(int[] nums) {
if (nums == null || nums.length < 2) {
return 0;
}
return sort(nums, 0, nums.length - 1, new int[nums.length]);
}
private long sort(int[] nums, int left, int right, int[] temp) {
if (left >= right) {
return 0;
}
int mid = left + (right - left) / 2;
return sort(nums, left, mid, temp)
+ sort(nums, mid + 1, right, temp)
+ merge(nums, left, mid, right, temp);
}
private long merge(int[] nums, int left, int mid, int right, int[] temp) {
int i = left;
int j = mid + 1;
int k = left;
long sum = 0;
while (i <= mid && j <= right) {
if (nums[i] < nums[j]) {
sum += (long) nums[i] * (right - j + 1);
temp[k++] = nums[i++];
} else {
temp[k++] = nums[j++];
}
}
while (i <= mid) {
temp[k++] = nums[i++];
}
while (j <= right) {
temp[k++] = nums[j++];
}
for (k = left; k <= right; k++) {
nums[k] = temp[k];
}
return sum;
}
}
func smallSum(nums []int) int64 {
if len(nums) < 2 {
return 0
}
return smallSumSort(nums, 0, len(nums)-1, make([]int, len(nums)))
}
func smallSumSort(nums []int, left, right int, temp []int) int64 {
if left >= right {
return 0
}
mid := left + (right-left)/2
return smallSumSort(nums, left, mid, temp) +
smallSumSort(nums, mid+1, right, temp) +
smallSumMerge(nums, left, mid, right, temp)
}
func smallSumMerge(nums []int, left, mid, right int, temp []int) int64 {
i, j, k := left, mid+1, left
var sum int64
for i <= mid && j <= right {
if nums[i] < nums[j] {
sum += int64(nums[i]) * int64(right-j+1)
temp[k] = nums[i]
i++
} else {
temp[k] = nums[j]
j++
}
k++
}
for i <= mid {
temp[k] = nums[i]
i++
k++
}
for j <= right {
temp[k] = nums[j]
j++
k++
}
for k = left; k <= right; k++ {
nums[k] = temp[k]
}
return sum
}
复杂度分析
- 时间复杂度：$O(n \log n)$。归并排序有 $O(\log n)$ 层，每层合并的总长度为 $n$。
- 空间复杂度：$O(n)$。临时数组占 $O(n)$，递归栈占 $O(\log n)$。
关键点总结
- 把“每对元素逐个判断”改写成“一个左值批量贡献给右侧一段”。
- 分治按下标切分，天然保证左半元素在原数组中位于右半元素之前。
nums[i] < nums[j]时才能统计；相等不贡献。- 排序不是副作用，而是上一层能够批量统计的必要条件。
- 算法会把原数组排成升序；若调用方要求保留输入，应先复制数组。
易错点总结
- 使用
<=会把相等元素错误计入；[1,1]的答案应为 0。- 右侧剩余数量是
right - j + 1，不要漏掉当前j。- 贡献的是左侧较小值
nums[i]，不是右侧值nums[j]。- 只把结果变量声明为
long不够，Java 乘法前也要先转成long。- 忘记写回有序结果，会破坏上层归并的统计前提。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 剑指 Offer 51. 数组中的逆序对 | 困难 | 与本题同一套模板，统计的是「对数」而非「元素和」，把乘法里的 nums[i] 换成 1 即可 |
| 315. 计算右侧小于当前元素的个数 | 困难 | 结果要按原下标逐个输出，因此归并时必须搬运下标而不能只搬值 |
| 493. 翻转对 | 困难 | 判定条件变成 nums[i] > 2 * nums[j]，与归并的取数顺序不再一致，必须在合并前单独扫一趟 |
| 327. 区间和的个数 | 困难 | 先转成前缀和数组再归并，统计的是落在区间内的前缀和之差，需要双指针维护上下两个边界 |
| 629. K 个逆序对数组 | 困难 | 反向问题：给定逆序对数量求排列个数，走的是动态规划加前缀和优化，与归并计数形成对照 |
| 148. 排序链表 | 中等 | 归并排序在链表上的实现，考的是找中点与合并时的指针操作，可用来夯实归并本身 |
| 面试题-最小交换次数（任意交换与相邻交换） | 困难 | 答案恰好等于逆序对数量，是把归并计数结论套用到交换次数上的经典转化 |