子数组累加和为aim(小于等于aim)的三个问题

累加和 = aim的最长子数组的长度(数组可+,-,0)；
累加和 = aim的最长子数组的长度(数组+)(只有正数)；
累加和 <= aim的最长子数组的长度(数组可+,-,0)；

累加和 `= aim`的最长子数组的长度(数组可`+`,`-`,`0`)；

这个题目使用HashMap来存储前面出现过的累加和的下标，具体过程如下:

使用变量sum表示从0位置开始一直加到i位置所有元素的累加和；
HashMap中key表示从arr最左边开始累加过程中出现过的sum值，value表示的是sum值出现最早的位置；、
假设当前元素为arr[i]，则sum += arr[i]，之前所有累加和为sum ，查看map中是否有sum - aim这个值，如果有，且对应value为j，那么就找到一个子数组累加和为aim的，且长度为 i - j + 1；
检查现在的sum 是否在map中出现，如果不存在，说明此时是第一次出现的，把(sum,i)加入到map中；
继续遍历数组；

很重要的一个地方就是一开始map中要存(0,-1)这个值，直观理解是一个数也没有的时候也可以累加出0
看下面例子:
[1,2,3,3] ， aim = 6；
如果没有存(0,-1)，累加到下标为2的时候，sum = 6 此时，sum - aim = 6 - 6 = 0，但是没有0这个累加和，就会忽略；


`1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18`	``` /**　O(n)时间 O(n)空间 */ static int getMaxLength(int[] arr,int aim){ if(arr == null

问题变式: 给定一个数组，求正数和负数个数相等最长子数组长度。
解: 把正数变成1，负数变成-1即可。

还有一个扩展问题:

题目:

定义数组的异或和的概念:
数组中所有的数异或起来，得到的结果叫做数组的异或和，比如数组{3, 2, 1}的异或和是: 3 ^ 2 ^ 1 = 0 。
给定一个数组arr，你可以任意把arr分成很多不相容的子数组，你的目的是: 分出来的子数组中，异或和为0的子数组最多。
请返回: 分出来的子数组中，异或和为0的子数组最多是多少?

解析: 可以利用这个思想找到最晚出现和0~i内异或和(假设为xor)同样异或和的更小的范围内最晚出现的位置，因为最后一个部分是异或和为0，且xor^0 = xor。
这里写图片描述

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 /** * dp[i] = max(dp[i-1],dp[k] + 1) k表示的是i 如果是最优划分中的最后一个部分的最后一个数的话，k是那个部分的开始的地方的前一个 * 从 0~i-1中异或还是 xor的最晚的位置 : * @param arr * @return */ static int maxEor(int[] arr){ HashMap<Integer,Integer>map = new HashMap<>();//存放某个异或和最晚出现的位置 int res = 0,xor = 0; int[] dp = new int[arr.length]; map.put(0,-1); for(int i = 0; i < arr.length; i++){ xor ^= arr[i]; if(map.containsKey(xor)){// 找到上一个异或和为xor的最晚出现的位置　　　因为xor^0 = xor int k = map.get(xor); //k dp[i] = k == -1 ? 1 : dp[k] + 1; } if(i > 0){ dp[i] = Math.max(dp[i],dp[i-1]); } map.put(xor,i); //每次都要put进去 res = Math.max(dp[i],res); } return res; }


`1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25`	/** * dp[i] = max(dp[i-1],dp[k] + 1) k表示的是i 如果是最优划分中的最后一个部分的最后一个数的话，k是那个部分的开始的地方的前一个 * 从 0~i-1中异或还是 xor的最晚的位置 : * @param arr * @return */ static int maxEor(int[] arr){ HashMap<Integer,Integer>map = new HashMap<>();//存放某个异或和最晚出现的位置 int res = 0,xor = 0; int[] dp = new int[arr.length]; map.put(0,-1); for(int i = 0; i < arr.length; i++){ xor ^= arr[i]; if(map.containsKey(xor)){// 找到上一个异或和为xor的最晚出现的位置　　　因为xor^0 = xor int k = map.get(xor); //k dp[i] = k == -1 ? 1 : dp[k] + 1; } if(i > 0){ dp[i] = Math.max(dp[i],dp[i-1]); } map.put(xor,i); //每次都要put进去 res = Math.max(dp[i],res); } return res; }

累加和 `= aim`的最长子数组的长度(数组`+`)(只有正数)；

这个和上面唯一的不同就是数组中只有正数，这里使用类似窗口移动的做法，给出两个指针，L、R表示窗口的左右边界，sum表示的是arr[L,R]之间的累加和，L，R一直往右动。

如果窗口内sum < aim，R就往右扩，并且sum += arr[R]；
如果窗口内sum > aim，L 就往右扩，并且sum -= arr[L]；
如果窗口内sum = aim，就说明这个窗口内累加和为sum ，此时记录最大值即可；

这里写图片描述


`1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17`	``` static int getMax(int[] arr,int aim){ if(arr == null

累加和 `<= aim`的最长子数组的长度(数组可`+`,`-`,`0`)；

两个数组sum和ends，sum[i]表示的是以arr[i]开头(必须包含arr[i])的所有子数组的最小累加和，对应的ends[i]表示的是取得这个最小累加和的右边界。一开始先求出sums数组和ends[]数组。
这里写图片描述

这个题目最精华的是左右边界不回退，就是说，如果从0位置扩到T区间，T+1区间不能扩了，此时不是回到1位置开始扩，而是舍弃0位置，看能不能由于舍弃0位置把T+1位置加进来：

这里写图片描述


`1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29`	``` static int getMaxLength2(int[] arr,int aim){ if(arr == null