Minimum Size Subarray Sum —

Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn't one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

题目大意：给定一个非负数组，和一个指定值，找出最小子数组长度使得这个子数组的和大于指定的值。

解题思路：采用滚动计算的思路，类似rolling hash的思想，首先累加数组元素，当大于指定元素时——>执行（从这个子数组的第一个数开始，循环减去这些数），遍历一遍，得到最小子数组长度。

    public int minSubArrayLen(int s, int[] nums) {

        if (nums == null||nums.length == 0) {

            return 0;

        }

        int min = 0,pos=0,len=Integer.MAX_VALUE;

        for (int i =0; i<nums.length; i++ ) {

            min+=nums[i];

            while(min>=s){

                if (len>i-pos+1) {

                    len=i-pos+1;

                }

                min-=nums[pos];

                pos++;

            }

        }

        return len==Integer.MAX_VALUE?0:len;

    }

巴特西

Minimum Size Subarray Sum —— LeetCode

最新文章

热门文章