LeetCode 补充题 8. 计算数组的小和
题目描述
:::fold-green 相关原题
✅ 计算数组的小和
牛客统计左侧小于等于当前值的元素，本文统计严格小于的元素。
:::
给定整数数组
nums。对于每个元素nums[j]，将它左侧所有严格小于它的元素相加，再把各个位置得到的和累加，结果称为数组的小和。请返回
nums的小和。相同数值不满足“严格小于”，不产生贡献。
示例 1：
输入：nums = [1,3,4,2,5]
输出：16
解释：各个位置的贡献分别为 0、1、4、1、10，总和为 16。
提示：
- 按元素在原数组中的左右关系统计，不能先排序再按新位置定义小和。
- 每一对满足 i < j 且 nums[i] < nums[j] 的位置，贡献一次 nums[i]。
- 要求时间复杂度为 O(n log n)，额外空间复杂度为 O(n)。
题意分析
对每个元素，累加它左边所有严格小于它的元素，再把这些结果相加。等价地，对每一对原下标
i < j，若nums[i] < nums[j]，就让左值nums[i]贡献一次。相等元素不贡献，空数组或只有一个元素时没有这样的数对，小和为零。
解法：归并排序统计跨区间贡献
核心思路
[!blue]
将区间按下标分成左右两半，一对元素要么都在左半，要么都在右半，要么左元素在左半、右元素在右半。前两类由递归统计，当前只需统计跨越两半的贡献。这三类互不重叠，合起来覆盖所有数对。
递归返回后两半均已升序排列，且各自仍只包含原来那一半的元素，所以跨段比较天然满足原下标左小右大。用
i、j指向两段尚未合并的最小值：若nums[i] < nums[j]，右段从j到right的所有值都更大，左值便贡献nums[i] * (right - j + 1)，随后取走这个左值。若
nums[i] >= nums[j]，当前右值不大于任何剩余左值，不会再与它们产生贡献，直接取走右值。相等时也必须这样处理：保留左值，等它遇到后面更大的右值再统计。已经取走的右值都不大于当前左值，因此不会漏算。合并结束后把有序结果写回原区间，供上一层继续批量统计。每一对合法元素只会在首次被分到左右两半的那层计入一次，既不会重复，也不会遗漏。
解题步骤
- 长度不足 2 时返回 0；否则申请一个与输入等长的临时数组，供所有递归层复用。
- 对区间
[left, right]递归处理左右两半，分别得到内部小和和有序结果。- 合并时，左值严格小于右值才批量累加贡献；否则先取右值。
- 一侧耗尽后复制另一侧剩余元素。这时已没有尚未统计的合法跨段数对，无需再增加贡献。
- 将临时数组中的当前区间写回，返回“左半小和 + 右半小和 + 跨段贡献”。
代码实现
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)$。
关键点总结
[!green]
- 按原下标分治保证左右关系，按数值归并支持批量统计，两种顺序各有作用。
- 一个左值可以贡献多次，次数就是右段尚未合并的元素数量。
- 相等时先取右侧，既排除相等数对，也保留左值对后续更大右值的贡献。
- 递归返回的不仅是小和，还要保证区间有序；代码会把原数组排成升序。
易错点总结
[!yellow]
- 不能把比较改成
<=，题目要求严格更小。- 右段剩余数量为
right - j + 1，包含当前j；累加的值是nums[i]，不是nums[j]。- 乘法前就要把左值转成
long/int64，只把结果变量设为 64 位无法避免乘法先溢出。- 小和按元素本身的值累加；若输入允许负数，合法贡献也可能为负，不能只保留正数贡献。
- 忘记写回有序区间，会使上一层无法根据当前右值判断所有剩余右值。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 315. 计算右侧小于当前元素的个数 | 困难 | 都在有序归并时批量累计跨区贡献，本题贡献是较小左值本身，原题只计较小元素数量。 |
| 剑指 Offer 51. 数组中的逆序对 | 困难 | 原题统计左大右小的对数，本题统计左小右大的加权贡献，严格比较方向与累计量都不同。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！