leetcode 209 Minimum Size Subarray Sum
z
 2018-03-08 23:55:24  

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous 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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int i=0;
        int j=0;
        int n = nums.length-1;
        int sum = 0;
        int ans = Integer.MAX_VALUE;
        while(i<=n && j<=n && i<=j){
            if(sum < s){
                sum += nums[j];
                j++;
            }
            while(sum >=s){
                ans = Math.min(j-i, ans);
                sum -= nums[i];
                i++;
            }
        }
        return ans == Integer.MAX_VALUE? 0: ans;
    }
}
  • 用两个指针一个执行最前面，一个指向最后面，sum之和大于s时，i++，且记录当前的长度（j-i）。否则 j++
  • 时间复杂度为O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int end = nums.length;
        int start = 0;
        int ans = 0;
        while(start <= end){
            int mid = start + ((end - start)>>1);
            if(findWindow(s, nums, mid)){
                ans = mid;
                end = mid-1;
                System.out.print(ans);
                
            }
            else{
                start = mid + 1;
            }
        }
        return ans;
    }
    public boolean findWindow(int s, int[] nums, int size){
        
        for(int i=0; i<nums.length-(size-1); i++ ){
            int j=i;
            int sum = 0;
            while(j<=i+size-1){
                sum += nums[j];
                j++;
            }
            if(sum >= s)
                return true;
        }
        return false;
    }
}
  • 用二分查找的方式来计算求size。