Smallest subarray with sum greater than a given value | GeeksforGeeks
Given an array of positive integers and a number positive x, find the smallest subarray with sum greater than the given value.
Notice whether there is condition that all are non-negative...This problem can be solved in O(n) time using the idea used in this post
Given an array of positive integers and a number positive x, find the smallest subarray with sum greater than the given value.
arr[] = {1, 4, 45, 6, 0, 19}
x = 51
Output: 3
Minimum length subarray is {4, 45, 6}
int smallestSubWithSum(int arr[], int n, int x){ // Initialize current sum and minimum length int curr_sum = 0, min_len = n+1; // Initialize starting and ending indexes int start = 0, end = 0; while (end < n) { // Keep adding array elements while current sum // is smaller than x while (curr_sum <= x && end < n) curr_sum += arr[end++]; // If current sum becomes greater than x. while (curr_sum > x && start < n) { // Update minimum length if needed if (end - start < min_len) min_len = end - start; // if minLen==1 break; // remove starting elements curr_sum -= arr[start++]; } } return min_len;}
A little different
滑动窗口 [left, right] 初始大小为0，滑动的规则如下：
若元素之和 < s，窗口右边沿向右延伸，直到 元素之和≥s 为止。
若元素之和 ≥ s，更新最小长度。然后窗口左边沿右移一位（即移除窗口中第一个元素），重复第1步。
public int minSubArrayLen(int s, int[] nums) { if (nums.length == 0) {
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; } }Solution 3: 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.
Pre-sum is sorted ==> all numbers are positive.
The trick is here, we do binary search(fro 0 to i) at same time we do pre-sum computation.
The trick is here, we do binary search(fro 0 to i) at same time we do pre-sum computation.
Build pre-sum array, and do binary search(0-i) at same time.
public int minSubArrayLen(int s, int[] nums) {
if(nums.length==0 || nums==null) return 0;
int min=Integer.MAX_VALUE;
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 j=binarySearch(0,i,sum[i+1]-s+1,sum);
if(j>-1){
min=Math.min(min,i-j+1);
}
}
}
return min==Integer.MAX_VALUE?0:min;
}
int binarySearch(int left, int right, int target, int[] sum) {
int result = -1;
while (left < right-1) {
int m = left + (right-left)/2;
if (sum[m] >= target) {
right = m-1;
} else if (sum[m] < target) {
left = m;
}
}
if (sum[right] < target) {
return right;
} else if (sum[left] < target) {
return left;
} else {
return -1;
}
}
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 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) { // each time, it need read two values 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; }
http://www.programcreek.com/2014/05/leetcode-minimum-size-subarray-sum-java/O(n*n)The outer loop picks a starting element, the inner loop considers all elements (on right side of current start) as ending element. Whenever sum of elements between current start and end becomes more than the given number, update the result if current length is smaller than the smallest length so far.
Find subarray with given sum
Given an unsorted array of nonnegative integers, find a continous subarray which adds to a given number.
O(n): two pointers window:
O(n^2)
Read full article from Smallest subarray with sum greater than a given value | GeeksforGeeks
int smallestSubWithSum(int arr[], int n, int x){ // Initilize length of smallest subarray as n+1 int min_len = n + 1; // Pick every element as starting point for (int start=0; start<n; start++) { // Initialize sum starting with current start int curr_sum = arr[start]; // If first element itself is greater if (curr_sum > x) return 1; // Try different ending points for curremt start for (int end=start+1; end<n; end++) { // add last element to current sum curr_sum += arr[end]; // If sum becomes more than x and length of // this subarray is smaller than current smallest // length, update the smallest length (or result) if (curr_sum > x && (end - start + 1) < min_len) min_len = (end - start + 1); // we can break this loop } } return min_len;}Given an unsorted array of nonnegative integers, find a continous subarray which adds to a given number.
O(n): two pointers window:
int subArraySum(int arr[], int n, int sum){ /* Initialize curr_sum as value of first element and starting point as 0 */ int curr_sum = arr[0], start = 0, i; /* Add elements one by one to curr_sum and if the curr_sum exceeds the sum, then remove starting element */ for (i = 1; i <= n; i++) { // If curr_sum exceeds the sum, then remove the starting elements while (curr_sum > sum && start < i-1) { curr_sum = curr_sum - arr[start]; start++; } // If curr_sum becomes equal to sum, then return true if (curr_sum == sum) { printf ("Sum found between indexes %d and %d", start, i-1); return 1; } // Add this element to curr_sum if (i < n) curr_sum = curr_sum + arr[i]; } // If we reach here, then no subarray printf("No subarray found"); return 0;}int subArraySum(int arr[], int n, int sum){ int curr_sum, i, j; // Pick a starting point for (i = 0; i < n; i++) { curr_sum = arr[i]; // try all subarrays starting with 'i' for (j = i+1; j <= n; j++) { if (curr_sum == sum) { printf ("Sum found between indexes %d and %d", i, j-1); return 1; } if (curr_sum > sum || j == n) break; curr_sum = curr_sum + arr[j]; } } printf("No subarray found"); return 0;}