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

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


题目

未排序正数数组中累加和为给定值的最长子数组长度
例如:[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;
    }
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 题目1 给定一个无需数组arr,其中元素可正,可负,可0,给定一个整数k。求arr的所有子数组中累加和为k的最长子...
    futurehau阅读 7,330评论 1 3
  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 14,349评论 0 33
  • 1. Two Sum 用hash可以得到O(n)时间的解法,用python中的enumerate函数,可以获得元素...
    Morphiaaa阅读 3,262评论 0 0
  • 分治方法 将问题划分成互不相交的子问题 递归地求解子问题 将子问题的解组合起来 动态规划(两个要素:最优子结构、子...
    superlj666阅读 3,468评论 0 0
  • 荒凉 在一条醉死梦生的路上 不知为何遇见了你 你来自何方 这条路又通往何方
    mydearyanyan阅读 2,463评论 0 1