题解 | #计算数组的小和#

• 借助 「归并排序」的思路。smallSum([1,3,4,2,5])实际就等于smallSum([1,3,4])+smallSum([2,5]) + smallSum_Merge。smallSum_Merge等于左半段数组中比右半段数组小的元素。在归并排序的merge过程中计算这个smallSum_Merge。
• 在merge时，左段数组和右段数组都是有序的了。当nums[i] <= nums[j]时，表示nums[i]比nums[j]~nums[end]的元素都要小。因此res需加上j及以后元素的个数 * nums[i]，即 res+=nums[i] * (end-j+1)。

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int len = sc.nextInt();
        int[] nums = new int[len];
        for(int i = 0; i < len ; i++) {
            nums[i] = sc.nextInt();
        }
        long res = mergeSort(nums,0,len-1);
        System.out.print(res); 
    }
    // 归并排序     返回值：数组从start到end的小和
    public static long mergeSort(int[] nums,int start,int end) {
        if(start >= end) {
            return 0;
        }
        int mid = (end - start)/2 + start;

        return mergeSort(nums,start,mid) 
            + mergeSort(nums,mid+1,end) 
            + merge(nums,start,mid,end);
    }
    // 合并 nums的[start,mid]和[mid+1,end]，这两段都是有序的
    public static long merge(int[] nums,int start,int mid ,int end){
        // 临时存放排序元素
        int[] temp = new int[end-start+1];
        int i = start, j = mid+1;
        int cur = 0;
        long res = 0;
        while(i <= mid && j <= end) {
            // 因为两边都是有序的，所以j及其后面有(end-j+1)个元素大于nums[i]
            res += nums[i] <= nums[j] ? nums[i] * (end-j+1) : 0;
            temp[cur++] = nums[i] <= nums[j] ? nums[i++] : nums[j++];
        }

        while(i <= mid) {
            temp[cur++] = nums[i++];
        }
        // 因为左侧已经全都被计算过了， 所以此处不再重复计算小和
        while(j <= end) {
            temp[cur++] = nums[j++];
        }

        // 替换掉nums数组的[start,end]段
        for(int num : temp) {
            nums[start++] = num;
        }
        return res;

    }



}