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

 public static void main(String[] args) {
        int[] nums = new int[]{1,3,4,2,5};
        System.out.println(getSmallSum(0, nums.length - 1, nums));

    }
    //合并两个数组，并计算左右差的小和
    static  int merge(int l, int mid, int r, int[] nums){

        //计算左右两块的和
        int l1 = l, r1 = mid + 1;
        int count = 0;
        while(l1 <= mid && r1 <= r){
            if(nums[l1] < nums[r1]){
                count += (r - r1 + 1) * nums[l1];
                l1++;
            }else{
                r1++;
            }
        }
        //合并两有序数组
        l1 = l;
        r1 = mid + 1;
        int[] temp = new int[r - l + 1];
        int index = 0;
        while(l1 <= mid && r1 <= r){
            if(nums[l1] < nums[r1]){
                temp[index++] = nums[l1++];
            }else{
                temp[index++] = nums[r1++];
            }
        }
        while(l1 <= mid){
            temp[index++] = nums[l1++];
        }
        while(r1 <= r){
            temp[index++] = nums[r1++];
        }

        //将有序数组恢复到原数组
        l1 = l;
        index = 0;
        while(l1 <= r){
            nums[l1++] = temp[index++];
        }

        return count;
    }

    //取数组的小和
    static  int getSmallSum(int l, int r, int[] nums){
        if(l == r){
            return 0;
        }
        int mid = (l + r) / 2;
        int left = getSmallSum(l, mid, nums);
        int right = getSmallSum(mid + 1, r, nums);
        int c = merge(l, mid, r, nums);
        return left + right + c;

    }