***干货:
子数组问题思路:必须以某个位置结尾的情况下怎么怎么样
双指针问题思路:算出来的一个指标可以指导我的双指针下一步应该怎么动
题目
未排序正数数组中累加和为给定值的最长子数组长度
例如:[1,2,3,1,1,1]目标值为3,那么最长长度为3
算法步骤
使用两个指针,left和right,记录从left到right之间的元素的值得和,使用一个变量res记录长度。如果这个和大于目标,那么left加一,如果这个和小于目标,那么right+1,如果这个值等于目标,那么比较并更新res,同时left++。
right超过最右边的时候结束循环
算法原理
假设客观条件下[left,right]为和为目标值的最长子数组,那么根据我们的策略首先left不会在right的右边,其次left也不会在区间内,最后left也不会在前边,因为在前边也会被最后移动过来。
代码
public static int getMaxLength(int[] arr,int target){
if(arr==null||arr.length==0||target<=0)
return 0;
int left=0;
int right=0;
int sum=0;
int len=0;
while(right<arr.length){
if(sum<target) {
right++;
if (right == arr.length)
break;
sum += arr[right];
}
else if(sum>target)
sum-=arr[left++];
else{
len=Math.max(len,right-left+1);
sum-=arr[left++];
}
}
return len;
}