LeetCode Q209 Minimum Size Subarray Sum | Lei Jiang Coding
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.
https://leetcode.com/discuss/35378/solutions-java-with-time-complexity-nlogn-with-explanation
https://leetcode.com/discuss/35626/java-solution-o-n-time-sliding-window
private int solveN(int s, int[] nums) {
int start = 0, end = 0, sum = 0, minLen = Integer.MAX_VALUE;
while (end < nums.length) {
while (end < nums.length && sum < s) sum += nums[end++];
if (sum < s) break;
while (start < end && sum >= s) sum -= nums[start++];
if (end - start + 1 < minLen) minLen = end - start + 1;
}
return minLen == Integer.MAX_VALUE ? 0 : minLen;
}
public int minSubArrayLen(int s, int[] a) { if (a == null || a.length == 0) return 0; int i = 0, j = 0, sum = 0, min = Integer.MAX_VALUE; while (j < a.length) { sum += a[j++]; while (sum >= s) { min = Math.min(min, j - i); sum -= a[i++]; } } return min == Integer.MAX_VALUE ? 0 : min; }
http://segmentfault.com/a/1190000003922961
X. Slide Window
O(n log n) running time, and extra O(n) space.
We first compute all the prefix sums, where prefixSum[i] denotes the sum of the first i integers, i >= 0. Under this notation, the index for the prefixSum array ranges from 0 to n.
Next, for each index i, we find the minimum length of a subarray starting from i + 1 (inclusive) of which the sum >= s, using binary search. Hence, the overall running time is O(n log n).
Remarks: A slight improvement in terms of performance will be narrowing down the range of the binary search even further. Instead of searching from i to end, one can search from j to end, where j > i. One needs to change the following binarySearch() function signature to incorporate this improvement.
Next, we move two pointers i and j. For each i, we find the minimum length of a subarraystarting from i + 1 (inclusive) of which the sum >= s. The key observation is that j is non-decreasing, which implies an algorithm with O(n) running time.
X. https://leetcode.com/discuss/63385/o-n-o-nlogn-solutions-both-o-1-space
http://www.programcreek.com/2014/05/leetcode-minimum-size-subarray-sum-java/
Read full article from LeetCode Q209 Minimum Size Subarray Sum | Lei Jiang Coding
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.
https://leetcode.com/discuss/35378/solutions-java-with-time-complexity-nlogn-with-explanation
https://leetcode.com/discuss/35626/java-solution-o-n-time-sliding-window
I think in the initialization,
min should be nums.length+1 instead of nums.length.
And at last, instead of
if(min == nums.length)return 0;
it should be
if(min == nums.length+1) return 0;
public int minSubArrayLen(int s, int[] a) { if (a == null || a.length == 0) return 0; int i = 0, j = 0, sum = 0, min = Integer.MAX_VALUE; while (j < a.length) { sum += a[j++]; while (sum >= s) { min = Math.min(min, j - i); sum -= a[i++]; } } return min == Integer.MAX_VALUE ? 0 : min; }
http://segmentfault.com/a/1190000003922961
我们用两个指针维护一个窗口，保证这个窗口的内的和是小于目标数的。如果新来的数加上后，和大于目标，则比较下当前窗口长度和最短窗口长度，窗口左边界右移。如果和仍小于目标数，则将窗口右边界右移。注意这里退出的条件，右边界是小于等于长度，因为我们窗口到了最右侧时，还需要继续左移左边界来看有没有更优的解法。另外，如果左边界大于右边界时，说明最短子串的长度已经小于等于1，我们就不用再查找了。
public int minSubArrayLen(int s, int[] nums) {
if(nums.length == 0) return 0;
int left = 0, right = 0, sum = 0, minLen = nums.length + 1;
while(right <= nums.length && left <= right){
if(sum < s){
// 当右边界等于长度时，我们要多等一轮，等待左边界左移，这时候不能加
if(right < nums.length){
sum += nums[right];
}
right++;
} else {
// 当和大于等于目标时，检查长度并左移边界
minLen = Math.min(minLen, right - left);
sum -= nums[left];
left++;
}
}
return minLen <= nums.length ? minLen : 0;
}X. Slide Window
public int minSubArrayLen(int s, int[] nums) { if (nums.length == 0) { return 0; } int totalSum = 0; for (int num : nums) { totalSum += num; } if (totalSum < s) { return 0; } int i = 0; int j = 0; int currSum = nums[0]; int minLen = nums.length; while (i < nums.length) { if (currSum >= s) { if (minLen > j - i + 1) { minLen = j - i + 1; } currSum -= nums[i]; i++; } else { j++; if (j >= nums.length) { break; } currSum += nums[j]; } } return minLen; }X. Prefix Sum + Binary Search
O(n log n) running time, and extra O(n) space.
We first compute all the prefix sums, where prefixSum[i] denotes the sum of the first i integers, i >= 0. Under this notation, the index for the prefixSum array ranges from 0 to n.
Next, for each index i, we find the minimum length of a subarray starting from i + 1 (inclusive) of which the sum >= s, using binary search. Hence, the overall running time is O(n log n).
Remarks: A slight improvement in terms of performance will be narrowing down the range of the binary search even further. Instead of searching from i to end, one can search from j to end, where j > i. One needs to change the following binarySearch() function signature to incorporate this improvement.
private int binarySearch(int i, int s, int[] prefixSum) { int low = i; int high = prefixSum.length - 1; while (low <= high) { int mid = low + (high - low) / 2; if (prefixSum[mid] - prefixSum[i] < s) { low = mid + 1; } else { if ( mid > 0 && prefixSum[mid - 1] - prefixSum[i] < s ) { return mid - i; } high = mid - 1; } } return prefixSum.length; } public int minSubArrayLen(int s, int[] nums) { if (nums.length == 0) { return 0; } int[] prefixSum = new int[nums.length + 1]; int totalSum = buildPrefixSum(nums, prefixSum); if (totalSum < s) { return 0; } int minLen = prefixSum.length - 1; for (int i = 0; i < prefixSum.length; i++) { int len = binarySearch(i, s, prefixSum); if (minLen > len) { minLen = len; } } return minLen; }
public int minSubArrayLenBinarySearch(int s, int[] nums) {
if (null == nums || nums.length == 0) {
return 0;
}
int min = nums.length + 1;
int[] sum = new int[nums.length + 1];
for (int i = 0; i < nums.length; i++) {
sum[i + 1] = sum[i] + nums[i];
if (sum[i + 1] >= s) {
int left = binarySearch(sum, sum[i + 1] - s, 0, i + 1);
min = Math.min(min, i + 1 - left);
}
}
return min == nums.length + 1 ? 0 : min;
}
private int binarySearch(int[] nums, int target, int start, int end) {
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (nums[mid] >= target) {
end = mid;
} else {
start = mid;
}
}
if (nums[end] <= target) {
return end;
} else {
return start;
}
}
X. O(n) running time, and extra O(n) space.We first compute all the prefix sums, where prefixSum[i] denotes the sum of the first i integers, i >= 0. Under this notation, the index for the prefixSum array ranges from 0 to n.Next, we move two pointers i and j. For each i, we find the minimum length of a subarraystarting from i + 1 (inclusive) of which the sum >= s. The key observation is that j is non-decreasing, which implies an algorithm with O(n) running time.
private int buildPrefixSum(int[] nums, int[] prefixSum) { prefixSum[0] = 0; for (int i = 0; i < nums.length; i++) { prefixSum[i + 1] = prefixSum[i] + nums[i]; } return prefixSum[nums.length]; } private int twoPointerIncrementalSearch( int s, int[] prefixSum ) { int minLen = prefixSum.length - 1; int i = 0; int j = 1; while ( i < prefixSum.length - 1 && j < prefixSum.length ) { if (prefixSum[j] - prefixSum[i] < s) { j++; } else { if (minLen > j - i) { minLen = j - i; } i++; } } return minLen; } public int minSubArrayLen(int s, int[] nums) { if (nums.length == 0) { return 0; } int[] prefixSum = new int[nums.length + 1]; int totalSum = buildPrefixSum(nums, prefixSum); if (totalSum < s) { return 0; } return twoPointerIncrementalSearch(s, prefixSum); }http://www.jyuan92.com/blog/leetcode-minimum-size-subarray-sum/
When meet some problem, which required to check / get the sub-continuous-array or sub-continuous-string, we should always think about Slide Window Algorithm.
Using two pointers, initial to the zero index.
- When the sum is smaller than
s, which means that we should move the right pointer to the next index. - When the sum is larger or equal than
s, which means the sum of subarray betweenleftandrightsatisfied the requirement. theright - left + 1maybe the result. Check for the result, and moveleftpointers to the next index. - We should always be careful about the edge case
- there isn’t exist a subarray which the sum will larger than
s - When right reach the last index of array, the left index should still keep moving if the sum is larger than
s. But when stop?! - When there exist an element which is equal or larger than s.
- there isn’t exist a subarray which the sum will larger than
- Time Complexity:
O(n)
The best solution is below, and we should keep in mind this solution as an template.
public int minSubArrayLenImprove(int s, int[] nums) {
if (null == nums || nums.length == 0) {
return 0;
}
int left = 0;
int right = 0;
int min = nums.length + 1;
int sum = 0;
while (right < nums.length) {
sum += nums[right];
while (sum >= s) {
min = Math.min(min, right - left + 1);
sum -= nums[left];
left++;
}
right++;
}
return min == nums.length + 1 ? 0 : min;
}
public int minSubArrayLen(int s, int[] nums) {
if (null == nums || nums.length == 0) {
return 0;
}
int left = 0;
int right = 0;
int sum = nums[0];
int minLength = Integer.MAX_VALUE;
while (right < nums.length) {
if (sum >= s) {
minLength = Math.min(minLength, right - left + 1);
sum -= nums[left];
left++;
} else {
if (right == nums.length - 1) {
return minLength == Integer.MAX_VALUE ? 0 : minLength;
}
right++;
sum += nums[right];
}
}
return minLength;
}
Another O(NLogN) solution that first calculate cumulative sum and then for each starting point binary search for end position. This uses O(N) space
public int minSubArrayLen(int s, int[] nums) {
int sum = 0, min = Integer.MAX_VALUE;
int[] sums = new int[nums.length];
for (int i = 0; i < nums.length; i++)
sums[i] = nums[i] + (i == 0 ? 0 : sums[i - 1]);
for (int i = 0; i < nums.length; i++) {
int j = findWindowEnd(i, sums, s);
if (j == nums.length) break;
min = Math.min(j - i + 1, min);
}
return min == Integer.MAX_VALUE ? 0 : min;
}
private int findWindowEnd(int start, int[] sums, int s) {
int i = start, j = sums.length - 1, offset = start == 0 ? 0 : sums[start - 1];
while (i <= j) {
int m = (i + j) / 2;
int sum = sums[m] - offset;
if (sum >= s) j = m - 1;
else i = m + 1;
}
return i;
}X. https://leetcode.com/discuss/63385/o-n-o-nlogn-solutions-both-o-1-space
O(NLogN) - search if a window of size k exists that satisfy the condition
public class Solution { public int minSubArrayLen(int s, int[] nums) { int i = 1, j = nums.length, min = 0; while (i <= j) { int mid = (i + j) / 2; if (windowExist(mid, nums, s)) { j = mid - 1; min = mid; } else i = mid + 1; } return min; } private boolean windowExist(int size, int[] nums, int s) { int sum = 0; for (int i = 0; i < nums.length; i++) { if (i >= size) sum -= nums[i - size]; sum += nums[i]; if (sum >= s) return true; } return false; } }
http://www.programcreek.com/2014/05/leetcode-minimum-size-subarray-sum-java/
for(int j=0; j<nums.length; ){ ==> not goodhttp://shibaili.blogspot.com/2015/06/day-107-minimum-size-subarray-sum.html
Read full article from LeetCode Q209 Minimum Size Subarray Sum | Lei Jiang Coding
