递归排序--leetcode 327.区间和的个数

327. 区间和的个数 - 力扣（LeetCode）

getSum(arr,i,j)这个方法是求arr在i~j的和

那如果要一直调用的话这个方法的时间复杂度就很高所以可以先生成一个arr数组的前缀和:

getSum(arr,i,j)=preSum[j]-preSum[i-1];

暴力递归：挨个枚举子数组

换换思路：

任何一个子数组一定会以一个位置结尾，整个数组arr，所有以0位置结尾的子数组，达标就找到一个，不达标就找了0个，再去求必须以1位置结尾的子数组满足条件有b个…一直求到以n-1位置结尾的子数组，如果求出以每个位置结尾达标的子数组的数量，每一步都求出正确的，那么都加起来就是要的总答案：

第一步转化：求每个位置结尾它的达标数量

如果sum(i…j)满足题意[lower,upper]，则sum(0…j)-sum(0…i-1)也一定在这个范围上，这是充分必要条件；

sum(0…17)=a

就想求以17位置结尾的子数组累加和的范围落在[10,40]这个范围上

假设知道0-17上的累加和100，那么之前也会有前缀和：（一个数也没有的时候、0-0、0-1、0-2…0-16)----17位置之前有多少个前缀和

那么以17位置结尾的子数组累加和有多少落在[10,40]这个范围上可以做一个转化：定出一个新的范围：[100-40,100-10]->[60-90] 就看17之前的前缀和中 有多少个范围是落在[60,90]这个范围上的，任何一个前缀和只要它落在这个范围上都一定可以转化出一个以17位置结尾的子数组来而且还是达标的：

比如：一个数也没有这个前缀和–0 它在不在这个范围上[60,90]，不在，所以我就知道[0,17]这个子数组它不达标，[0-17]是整个前缀和再减去一个一个数也没有的前缀和，剩下啥？剩下它自己，但是一个数也没有的时候不符合这个目标，所以一个数也没有减完，它自己这个子数组是不达标的；

就是都用0-17范围上的一个整体的前缀和减去一个之前的前缀和就可以转化出剩下子数组的前缀和；

假设0-0范围上的累加和：40，那么0-17上的累加和-0-0上的累加和得到1-17上的这个子数组，因为0-0范围上没有落在[60,90]这个目标里，所以减完之后的子数组它也必然不会落在原始目标里[10，40]；

假设0-1上的前缀和是70落在这个范围上了[60,90]，那么减完之后的子数组必达标，0-17上的子数组前缀和是100减完0-1范围上的前缀和70剩下30，30就是2-17范围的累加和，一个前缀和在[60,90]范围上的达标一定可以找到一个17位置结尾的子数组在原始范围上达标的情况；

整个题目这五步连下来理解：

 * ----------------------------题解二：
 * 这道题目最好解的方法是通过有序表来解：treeMap
 * 通过有序表来解决比通过归并排序来解决少绕了很多弯路
 * sum[]是前缀和数组 就想让我这个前缀和数组从左往右遍历
 * 当我遍历到100的时候 此时假设我有一种结构
 * 把之前所有的前缀和都放到这种结构里 这种结构它是一个有序表
 * 之前的所有前缀和都在这个有序表里
 * 这个结构首先加进去一个数组织成有序的性能很高 是 O(logN)水平
 * 现在100来了 我要查的东西是
 * [100-upper~100-lower]这个范围上
 * 在这个有序表收集到所有数据中有多少个数处在这个范围上
 * 如果能够实现这个结构能够告诉我有多少个数落在这个范围上[100-upper,100-lower]
 * 那么就简单多了 假设有某个结构出现一个前缀和就加进去
 *

package class05;

// 这道题直接在leetcode测评：
// https://leetcode.com/problems/count-of-range-sum/

/**
 * 第一步转化：求每个位置结尾它的达标数量
 *
 * 如果sum(i...j)满足题意[lower,upper]，则sum(0...j)-sum(0...i-1)也一定在这个范围上，这是充分必要条件；
 *
 * sum(0...17)=a
 *
 * 就想求以17位置结尾的子数组累加和的范围落在[10,40]这个范围上
 *
 * 假设知道0-17上的累加和100，那么之前也会有前缀和：（一个数也没有的时候、0-0、0-1、0-2...0-16)----17位置之前有多少个前缀和
 *
 * 那么以17位置结尾的子数组累加和有多少落在[10,40]这个范围上可以做一个转化：定出一个新的范围：[100-40,100-10]->[60-90] 就看17之前的前缀和中 有多少个范围是落在[60,90]这个范围上的，任何一个前缀和只要它落在这个范围上都一定可以转化出一个以17位置结尾的子数组来而且还是达标的：
 *
 * 比如：一个数也没有这个前缀和--0 它在不在这个范围上[60,90]，不在，所以我就知道[0,17]这个子数组它不达标，[0-17]是整个前缀和再减去一个一个数也没有的前缀和，剩下啥？剩下它自己，但是一个数也没有的时候不符合这个目标，所以一个数也没有减完，它自己这个子数组是不达标的；
 *
 * 就是都用0-17范围上的一个整体的前缀和减去一个之前的前缀和就可以转化出剩下子数组的前缀和；
 *
 * 假设0-0范围上的累加和：40，那么0-17上的累加和减去0-0上的累加和得到1-17上的这个子数组，因为0-0范围上没有落在[60,90]这个目标里，所以减完之后的子数组它也必然不会落在原始目标里[10，40]；
 *
 * 假设0-1上的前缀和是70落在这个范围上了[60,90]，那么减完之后的子数组必达标，0-17上的子数组前缀和是100减完0-1范围上的前缀和70剩下30，30就是2-17范围的累加和，一个前缀和在[60,90]范围上的达标一定可以找到一个17位置结尾的子数组在原始范围上达标的情况；
 *
 *
 * 假设0-i整体累加和是x 题目[L,up]
 * 求必须以i位置结尾的子数组，目标有多少个在[L,up]范围上，
 * 等同于去求i之前的所有前缀和中有多少前缀和在[x-up,x-L]上
 *
 * 原始arr处理成一个前缀和数组 叫做sum[]，sum里全是前缀和数组，
 * 把原始arr忘记掉，因为这个不需要这个原始数组了
 * 只留下前缀和数组，这个数组我们求什么？
 * 求这个前缀和数组sum中出现的每一个数x，它之前有多少个数落在x-up上到x-l上
 * 下一个数假设是y就求y之前有多少个数落在y-up到y-l上
 * 再下一个数如果是z 就求z之前有多少个数落在z-up到z-l上
 * 现在已经可以把原数组arr给忘掉了 只留下前缀和数组求这么一件事
 *
 * 列举一个前缀和数组：sum[]
 * 假设归并排序排完了之后
 * 左组：[1,3,4,4,5] 右组：[2,7,8,8,9] 原始目标是：[0,5]
 * 目的是在左组和右组merge的过程中求出每一个右组在左组范围上达标的数量
 * 说的仔细一点：
 * 对于右组的数2来说它想知道左组有多少个数落在 2-5~2-0 <-> -3~2 范围上
 * 对于右组的数7来说它想知道左组有多少个数落在 7-5~7-0 <->  2~7 范围上
 * 对于右组的数8来说它想知道左组有多少个数落在 8-5~8-0 <->  3~8 范围上
 *
 * 我自己一些小想法来理解这道题：
 * 求sum(arr,i,j)∈[lower,upper]->
 * preSum(j)-preSum(i-1)∈[lower,upper]->
 * preSum(i-1)∈[preSum(j)-upper,preSum(j)-lower] (i<=j) ①
 * 原题目就是问：数组preSum中满足①式的(i,j)数对的有多少对：
 * 那么：
 * j刚好非常便利的看作递归中右组中的某一个数
 * i刚好非常便利的看作递归中左组中的某一个数
 * 			// [L...R] L...R之间的数就是 R-L+1
 * 			// [L...R) L...R之间的数就是 R-L
 * 			// 这个应该当成结论来记住
 * 			// R - L 就是求个数
 * 			// 13 14 15 16 17
 * 			// [14,14)表示一个数也没有 14-14=0;
 * 			// [14,14]表示有一个数 14-14+1=0;
 * 			// [14,16)表示有两个数 16-14=2；
 *
 *
 *
 * ----------------------------题解二：
 * 这道题目最好解的方法是通过有序表来解：treeMap
 * 通过有序表来解决比通过归并排序来解决少绕了很多弯路
 * sum[]是前缀和数组 就想让我这个前缀和数组从左往右遍历
 * 当我遍历到100的时候 此时假设我有一种结构
 * 把之前所有的前缀和都放到这种结构里 这种结构它是一个有序表
 * 之前的所有前缀和都在这个有序表里
 * 这个结构首先加进去一个数组织成有序的性能很高 是 O(logN)水平
 * 现在100来了 我要查的东西是
 * [100-upper~100-lower]这个范围上
 * 在这个有序表收集到所有数据中有多少个数处在这个范围上
 * 如果能够实现这个结构能够告诉我有多少个数落在这个范围上[100-upper,100-lower]
 * 那么就简单多了 假设有某个结构出现一个前缀和就加进去
 *
 */
public class Code01_CountOfRangeSum {

	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) {
			// 只有一个数无需进行归并
			// 也就是0...R这个子数组的累加和是否直接就满足[lower,upper]
			return sum[L] >= lower && sum[L] <= 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) ----------------整个过程O(n)
		for (int i = M + 1; i <= R; i++) {
			// 循环过程中 windowL 和 windowR都是不会回退的
			// 因为[arr[i]-upper,arr[i]-lower] 中arr[i]随着i是单调递增的
			// 所以这个范围随着i也是单调递增
			// 所以windowL 和 windowR也不用回退
			// 可以保持上次循环结束的值下一次接着走
			long min = arr[i] - upper;
			long max = arr[i] - lower;
			//---求左组上满足min~max范围上总共有几个数
			while (windowR <= M && arr[windowR] <= max) {
				//使得右边界windowR一定是刚好比max大的位置
				windowR++;
			}
			while (windowL <= M && arr[windowL] < min) {
				//使得左边界windowL一定是刚好小于min的位置
				windowL++;
			}
			// [L...R] L...R之间的数就是 R-L+1
			// [L...R) L...R之间的数就是 R-L
			// 这个应该当成结论来记住
			// R - L 就是求个数
			// 13 14 15 16 17
			// [14,14)表示一个数也没有 14-14=0;
			// [14,14]表示有一个数 14-14+1=0;
			// [14,16)表示有两个数 16-14=2；
			ans += windowR - windowL;
			//---求左组上满足min~max范围上总共有几个数
		}
		// [windowL, windowR) ----------------整个过程O(n) 因为窗口不回退
		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;
	}

}