你的位置:首页 > Java教程

[Java教程][LeetCode] 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.

     这道题主要还是先要把题目的要求弄清楚。首先题目中所说的if there is not one, return 0 instead。怎样才算是没有呢?

     这里意思是如果我们算出来的min length和array本身的长度一样,那么我们就应该return 0。

     这里比较容易想到的是用two pointer来计算。一个pointer用来计算sum,和另一个pointer紧随其后,用来判断长度。

     代码如下。~

public class Solution {  public int minSubArrayLen(int s, int[] nums) {    //two pointer     //one from start;one follows    int start = 0;     int end = 0;          int sum = 0;     int min = nums.length;          while(start<nums.length && end<nums.length) {       while(sum<s && end<nums.length) {         sum=sum+nums[end];        end++;      }       while(sum>=s && start<=end) {         min = Math.min(min, end-start);         sum =sum-nums[start];        start++;      }     }     if(min==nums.length){      return 0;    }    return min;  }}