总结
题目一主要技巧：利用单调性优化。
题目二主要技巧：利用预处理结构优化。
题目三主要技巧：假设答案法+淘汰可能性（很难，以后还会见到）。
- 给定一个正整数组成的无序数组arr，给定一个正整数值K，找到arr的所有子数组里，哪个子数组的累加和等于K，并且是长度最大的返回其长度。
/**
* 给定一个正整数组成的无序数组arr，给定一个正整数值K
* 找到arr的所有子数组里，哪个子数组的累加和等于K，并且是长度最大的
* 返回其长度
*/
public class ArrayProblem1 {
// 由于都是正整数，所以子数组具有单调性增加子数组的长度值必增大
// 减小子数组的长度值必减小，所以可以利用滑动窗口来解。
/**
* 流程：
* 1. L R 为滑动窗口的边界，sum为滑动窗口的累加和
* 2.若累加和大于K，L向右移动，
* 3.若累加和小于K，R向右移动，
* 4.若累加和等于K，找到一个答案，收集此时的长度。
* 实质：
* 当累加和等于K时，其实就是找到了以L为头的累加和等于K的最长子数组，若R向右移动则累加和必超过K，不会有更长的了
*/
public static int arrayProblem(int[] arr,int k){
if(arr == null || arr.length == 0 || k < 0){
return 0;
}
// 定义窗口边界
int L = 0;
int R = 0;
int len = 0;
int sum = arr[0];
int n = arr.length;
while (L < n && R < n){
if(sum > k){
// L向右移动，移动之前先要把累加和减掉
sum -= arr[L++];
}else if(sum < k){
// R向右移动
if(++R >= n){
break;
}
sum += arr[R];
}else{
// 结算
len = Math.max(len,R - L + 1);
// 这里R 向右动，和L向右动都可以没有区别，R向右动后sum必大于k,接下来L会向右动
// 若是L向右动，sum必小于K，接下来R必向右动。
sum -= arr[L++];
}
}
return len;
}
}
- 给定一个整数组成的无序数组arr，值可能正、可能负、可能0，给定一个整数值K，找到arr的所有子数组里，哪个子数组的累加和等于K，并且是长度最大的，返回其长度。
/**
* 给定一个整数组成的无序数组arr，值可能正、可能负、可能0
* 给定一个整数值K
* 找到arr的所有子数组里，哪个子数组的累加和等于K，并且是长度最大的
* 返回其长度
*/
public class ArrayProblen2 {
// 由于数组中有正有负有0，不具有单调性，滑动窗口或者双指针已经不能用了
// 利用预处理结构。
/**
* 求数组问题一般有有两种思路，1.以位置开头满足条件的情况。2.以i位置结尾满足条件的情况。数组问题已就属于1
* 流程：我们以i位置结尾来分。
* 1.要求以i位置结尾的累加和等于K的最长子数组，加入此时以i位置结尾，从0位置到i位置的累加和是sum = 1000,且K = 800
* 那么要使得i位置结束最长，那么从0位置开始到某个位置X累加和为200要最先形成，此时0~X的位置时最早形成200的，那么X+1 ~
* i 就是最长的满足条件的长度。记录每个长度选出最大值。
*
*/
public static int arrayProblem3(int[] arr,int k){
if(arr == null || arr.length ==0){
return 0;
}
// 记录第一次累加和出现的位置
Map<Integer,Integer> map = new HashMap<>();
// 初始化map ,前缀和为0的点在-1位置
map.put(0,-1);
int index = 0;
int len = 0;
int sum = arr[index];
int n = arr.length;
while (index < n){
int temp = sum - k;
// 最早前缀和不包含就添加
if(!map.containsKey(sum)){
map.put(sum,index);
}
if(map.containsKey(temp)){
// 包含
len = Math.max(len,index - map.get(temp));
}
if(++index >= n){
break;
}
sum += arr[index];
}
return len;
}
}
扩展：一个整数数组中，有正有负，有0，包含2的个数和1的个数相等的子数组为达标子数组，问在所有的达标子数组中最长的长度是多少。
1.思路：遍历数组把不等于1和2的数字全部变为0，1变-1，2变1，把问题变成找和为0的最长子数组的问题。给定一个整数组成的无序数组arr，值可能正、可能负、可能0,给定一个整数值K
找到arr的所有子数组里，哪个子数组的累加和<=K，并且是长度最大的,返回其长度
public class ArrayProblen3 {
public static int arrayProblen3(int[] arr,int k){
if(arr == null || arr.length == 0){
return 0;
}
// 预处理，生成最小子数组和组成的数组minSum,minSum[i]代表以i为头的最小子树的和是多少
// 还有一个预处理数组叫做最小子数组的有边界数组，minSumIndex,minSumInde[i]代表以开头的最小子数组的右边界的位置
int n = arr.length;
// 从数组尾部开始生成预处理数组，最后一元素可以直接确定最小和，和有边界。
int[] minSum = new int[n];
int[] minSumIndex = new int[n];
minSum[n-1] = arr[n-1];
minSumIndex[n-1] = n - 1;
for (int i = n - 2; i >= 0; i--) {
// 如果当前元素的后一个元素的minSum[i + 1] > 0,那么以开始的最小子数组和就是自己，边界也是i
// 否则minSum[i] = arr[i] + minSum[i+1],minSumIndex[i] = minSumIndex[i+1]
if(minSum[i+1] >= 0){
minSum[i] = arr[i];
minSumIndex[i] = i;
}else{
minSum[i] = arr[i] + minSum[i+1];
minSumIndex[i] = minSumIndex[i+1];
}
}
int sum = 0;
int end = 0;
int len = 0;
for (int i = 0; i < n; i++) {
// 如果sum小于k，那么一直让sum往右扩
while (end < n && (sum + minSum[end]) <= k){
sum += minSum[end];
end = minSumIndex[end]+1;
}
// 跳出循环此时算上end开头的部分就会超过k,那就让i++,看看能不能继续向右扩,i++前先收集答案
len = Math.max(len,end - i);
if(end > i){
sum -= arr[i];
}else{
end = i + 1;
}
}
return len;
}
}
