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

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

作者: futurehau | 来源:发表于2016-08-06 14:26 被阅读159次

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


题目

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

相关文章

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

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

  • 未排序数组中累加和为给定值的最长子数组系列问题

    题目1 给定一个无需数组arr,其中元素可正,可负,可0,给定一个整数k。求arr的所有子数组中累加和为k的最长子...

  • 【python程序员代码面试指南】未排序数组中累加和为给定值得最

    题目:给定一个无序数组arr, 其中元素可正、可负、可0。给定一个整数k,求arr所有子数组中累加和为k的最长子数...

  • leetcode--128--最长连续序列

    题目:给定一个未排序的整数数组 nums ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。 进阶:...

  • LintCode 80 [Median]

    原题 给定一个未排序的整数数组,找到其中位数。中位数是排序后数组的中间值,如果数组的个数是偶数个,则返回排序后数组...

  • 128:最长连续序列

    题意 给定一个未排序的整数数组 nums ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。 请你设...

  • LeetCode 128. 最长连续序列

    题目 给定一个未排序的整数数组 nums ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。请你设计...

  • Lintcode-中位数

    问题描述: 给定一个未排序的整数数组,找到其中位数。中位数是排序后数组的中间值,如果数组的个数是偶数个,则返回排序...

  • Day66 最长连续序列

    给定一个未排序的整数数组 nums ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度 进阶:你可以设...

  • 中位数

    给定一个未排序的整数数组,找到其中位数。中位数是排序后数组的中间值,如果数组的个数是偶数个,则返回排序后数组的第N...

网友评论

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

      本文链接:https://www.haomeiwen.com/subject/akmksttx.html