题目1
给定一个无需数组arr,其中元素可正，可负，可0，给定一个整数k。求arr的所有子数组中累加和为k的最长子数组的长度。
思路
首先注意到这里元素可正可负可0，所以之前的两个指针的方法不再有效，这里需要使用一种全新的方法，联想到之前说过的数组问题可以考虑必须以j结尾的情况下怎么怎么样，所以这个题按这种思路进行下去。
假设我们能得到以必须以位置j结尾的满足条件的最长子序列，那么我们从这些最长中找到一个最大即为所求，那么怎么求解以位置j结尾的累加和为k的最长子序列呢？我们假设
sum[j]为从0累加到j的和，那么以位置j结尾的满足条件的最长子序列的开头就应该是从0开始第一次出现累加和为sum[j]-k的位置i,也就是sum[i]+target=sum[j],这里sum代表从开始的累加和。
算法流程
- 记录一个全局最大res，记录一个sum表示从0位置一直加到当前位置的累加和，使用一个map来记录前边遍历过程中出现过的累加和。
- 遍历数组，对于当前位置i,首先更新sum，然后看map中有没有sum-k这个键，如果有，则取出这个键对应的值j,表明(i,j]这一小段子序列的和就为k,用这个k去更新我们的res。遍历结束之后res就为我们的最大。如果没有，这把这个位置和sum放入map中。
- 需要特别注意的是首先要把(0,-1)放进map中。比如arr=[5,-1,-1,-1],k=5,如果不放入(0,-1)，在考察位置0的时候，其实刚好这个和是满足条件的，但是被忽略了。
算法原理
这里的map记录的是累加和第一次出现某个值的位置。我们在遍历到j的时候，知道sum[j]=0,1,2,,,j的这些元素的累加和,sum[i]为0,1，，，，i这些数的累加和。考察位置j,我们需要找到第一次累加和为sum[j]-k的位置，如果找到了这个位置，那么就有i+1,i+2，...j这些元素的累加和为k,也就求得了以位置j结尾的累加和为k的最长子序列。我们遍历了数组一遍，所有位置结尾的，如果有满足条件的子序列，都求出来了，在这些中的最长的即为所求。
代码
public static int maxLength(int[] arr, int k) {
if(arr==null||arr.length==0)
return 0;
int sum=0;
int res=0;
Map<Integer,Integer> map=new HashMap<Integer,Integer>();
map.put(0,-1);
for(int i=0;i<arr.length;i++){
sum+=arr[i];
if(map.containsKey(sum-k)){
res=Math.max(i-map.get(sum-k),res);
}
if(!map.containsKey(sum))
map.put(sum,i);
}
return res;
}
题目拓展
1. 给定一个无需数组arr,其中元素可正，可负，可0，求arr中所####有正数与负数个数相等的最长子数组长度。
可以这样想，原数组中正数就变为1，负数就变为-1,0就为0，另k等于0，调用上述方法即可。
2. 给定一个无需数组arr,其中元素只能为1或0，求arr所有子数组中0和1个数相等的最长子数组的长度。
1为1,0为-1，k为0,调用上述求解和为k的最长子数组算法即可。
题目2
未排序数组中，累加和小于或等于给定值的最长子数组长度。
例如：arr=[3,-2,-4,0,6],k=-2,则累加和小于或等于-2的最长子数组的长度为4。[3,-2,-4,0]
思路
和之前的区别是，这里累加和是小于等于k,那么借助于之前的思路，我们考虑以位置j结尾的累加和小于等于k的最长子数组的长度，我们自然可以想到，需要寻找第一个累加和大于等于k的位置（之前的思路是第一个等于k的位置，我们是借助于一个map来实现的）那么这里怎么办呢？由于我们只关心第一个大于某个值的位置，所以我们可以借助一个阶梯上升的辅助数组h来实现，h[i]表示从开始位置到当前位置的最大累加和。这样在寻找第一个大于某个值得位置时，我们只需要二分来搜索即可。
arr: 3 2 -3 2 -2 6 -3 1
sum: 3 5 2 4 2 8 5 6
h: 3 5 5 5 5 8 8 8
算法流程&原理
使用一个辅助数组h,h[i]表示从开始到i位置的数组的子数组的最大和（不包括i位置）。然后遍历数组，二分查找第一个大于sum-k的位置，找到则更新，找不到继续。
之前一直不明白为什么h需要h[0]为0,然后长度为len+1，现在终于想明白了，因为我们求得第一个大于等于sum-k的位置，之前的方法h[i]包含了i位置的和，所以
3 2 -1 2 4 5 6 -1 5
3 5 4 6 10 15 21 20 25
3 5 5 6 10 15 21 21 25
比如说现在计算21这个位置，假设k为16，那么就需要求第一个大于等于5的位置i，并且这个位置我们是不能要的，这样i+1...j位置的和才会小于等于16。假设我们h[i]记录的就是0...i的这个递增的数组的话，比如上边h[1]表示加到h[1]最大和为5，我们不应该要h[1]而应该从h[2]开始，但是假设某些情况下h[2]也不满足条件，这就很麻烦了（3 2 0 2 4 5 6 -1 5），所以我们让h[i]为[0,i）的，不包含位置i,我们找到一个位置后，可以知道这个位置的前面是大于等于5的，这个位置就一定是满足条件的。
代码
public static int maxLength(int[] arr, int k) {
if(arr==null||arr.length==0)
return 0;
int[] h=new int[arr.length+1];
h[0]=0;
int sum=arr[0];
for(int i=1;i<arr.length;i++){
sum+=arr[i];
h[i+1]=Math.max(sum,h[i]);
}
int res=0;
int len;
int index;
sum=0;
for(int i=0;i<arr.length;i++){
sum+=arr[i];
index=firstBiggerOrEqual(h,sum-k);
len=index==-1?0:i-index+1;
res=Math.max(res,len);
}
return res;
}
public static int firstBiggerOrEqual(int[] h,int num){
int left=0;
int right=h.length-1;
int res=-1;
while(left<=right){
int mid=(left+right)/2;
if(h[mid]>=num){
res=mid;
right=mid-1;
}
else{
left=mid+1;
}
}
return res;
}
