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)