209 Minimum Size Subarray Sum

209. Minimum Size Subarray Sum​
1. Question
Given an array ofnpositive integers and a positive integers, find the minimal length of acontiguoussubarray of which the sum ≥s. If there isn't one, return 0 instead.
For example, given the array[2,3,1,2,4,3]ands = 7,
the subarray[4,3]has the minimal length under the problem constraint.
2. Implementation
(1) Two Pointers
1
class Solution {
2
    public int minSubArrayLen(int s, int[] nums) {
3
        int sum = 0, minLen = Integer.MAX_VALUE;
4
​
5
        for (int start = 0, end = 0; end < nums.length; end++) {
6
            sum += nums[end];
7
​
8
            while (sum >= s) {
9
                minLen = Math.min(minLen, end - start + 1);
10
                sum -= nums[start];
11
                ++start;
12
            }
13
        }
14
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
15
    }
16
}
Copied!
(2) Binary Search
1
class Solution {
2
    public int minSubArrayLen(int s, int[] nums) {
3
        int n = nums.length;
4
        int[] prefixSum = new int[n + 1];
5
​
6
        for (int i = 1; i <= n; i++) {
7
            prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
8
        }
9
​
10
        int minLen = Integer.MAX_VALUE;
11
​
12
        for (int i = 0; i < n; i++) {
13
            int index = binarySearch(prefixSum, i + 1, n, prefixSum[i] + s);
14
​
15
            if (index != -1) {
16
                minLen = Math.min(minLen, index - i);
17
            }
18
        }
19
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
20
    }
21
​
22
    public int binarySearch(int[] prefixSum, int start, int end, int target) {
23
        int mid = 0;
24
​
25
        while (start + 1 < end) {
26
            mid = start + (end - start) / 2;
27
​
28
            if (prefixSum[mid] < target) {
29
                start = mid + 1;
30
            }
31
            else {
32
                end = mid;
33
            }
34
        }
35
​
36
        if (prefixSum[start] >= target) {
37
            return start;
38
        }
39
        else if (prefixSum[end] >= target) {
40
            return end;
41
        }
42
        else {
43
            return -1;
44
        }
45
    }
46
}
Copied!
3. Time & Space Complexity
Two Pointers: 时间复杂度O(n), 空间复杂度O(1)
Binary Search: 时间复杂度O(nlogn), 空间复杂度O(1)

202 Happy Number

259 3Sum Smaller

Last modified 2yr ago

Copy link

Contents

209. Minimum Size Subarray Sum

1. Question

2. Implementation

3. Time & Space Complexity

209. Minimum Size Subarray Sum​

1. Question

2. Implementation

3. Time & Space Complexity

209. Minimum Size Subarray Sum