未排序整数数组中累加和为给定值的最长子数组长度(TwoPoint

2016-08-06  本文已影响159人  futurehau

***干货:
子数组问题思路:必须以某个位置结尾的情况下怎么怎么样
双指针问题思路:算出来的一个指标可以指导我的双指针下一步应该怎么动


题目

未排序正数数组中累加和为给定值的最长子数组长度
例如:[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;
    }
上一篇 下一篇

猜你喜欢

热点阅读