归并排序提高

1.CountOfRangeSum

给定一个数组arr，和两个整数lower和upper，返回arr中有多少个子数组的累加在[lower,upper]范围上 // https://leetcode.com/problems/count-of-range-sum/

• 前缀数组的运用，i到j位置的和是多少，用前缀和
• 求以i位置结尾的子数组，目标有多少个在[lower , upper] = 求i之前的所有前缀和中有多少个前缀和在[X - upper , X - lower]
• [1,3,4,4,5] | [2,7,8,8,9] 范围是【0，5】
• 当右组指向2时，看左组有多少个数字落在【0,3】上
• 由于每组是有序的，范围的上限和下限都不会回退

public static int countRangeSum(int[] nums , int lower , int upper){
        if (nums == null || nums.length == 0) return 0;
        //求前缀和
        long[] sum = new long[nums.length];
        sum[0] = nums[0];
        for (int i = 1 ; i < nums.length ; i++) {
            sum[i] = sum[i - 1] + nums[i];
        }
        return process(sum , 0 , sum.length - 1 , lower , upper);
    }

    public static int process(long[] sum, int L, int R, int lower, int upper){
        if (L == R){
            return sum[L] >= lower && sum[R] <= upper ? 1 : 0;
        }
        int M = L + ( (R - L) >> 1);
        return process(sum, L, M, lower, upper) + process(sum , M + 1 , R , lower , upper) +
                merge(sum , L , M , R , lower , upper);
    }

    public static int merge(long[] arr, int L, int M, int R, int lower, int upper){
        int ans = 0;
        int windowL = L;
        int windowR = L;
        // [windowL, windowR)
        //这样的话本来【13,15】的，就是求得[13 , 16），不用+1
        for(int i = M + 1 ; i <= R ; i++){
            long min = arr[i] - upper;
            long max = arr[i] - lower;
            while (windowR <= M && arr[windowR] <= max) windowR++;  //要大于max才会++
            while (windowL <= M && arr[windowL] < min) windowL++;   //
            ans += windowR - windowL;
        }

        long[] help = new long[R - L + 1];
        int i = 0 ;
        int p1 = L;
        int p2 = M + 1;
        while (p1 <= M && p2 <= R){
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= M){
            help[i++] = arr[p1++];
        }
        while (p2 <= R){
            help[i++] = arr[p2++];
        }
        for (i = 0 ; i < help.length ; i++){
            arr[L + i] = help[i];
        }
        return ans;
    }

2.快速排序_荷兰国旗

• 一个数组，小于等于X的在左边，大于X在右边
• 不能用辅助数组，时间复杂度为O(N)