Minimum Size Subarray Sum LT209
2024-08-27 05:47:47
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.
Example:
Input:s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray[4,3]has the minimal length under the problem constraint.
Follow up:
If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).
Idea 1. Sliding window, since numbers are positive, it means the prefix sum of subarrays is monotonic increasing. We can use either left or right side of window as the base to slide the window.
Time complexity: O(n)
Space complexity: O(1)
Take the left side as base, we need to find the smallest right index such that the sum[left..right] <= s, if the sum is smaller than s, we keep expanding right until the sum <= s, if such right index is found, the window size right - left + 1 is the minimum length of subarray starting at index left.
Note 1. when the termindation for find the right index has two conditions: right < nums.length && sum + nums[right] < s, the for loop terminates could mean just reaching the end of the array, might not mean the subarray sum >= s, hence we need to add extra check.
Note 2: The toal sum of the whole array could be less than k, in this case, such subarray doesn't exist.
class Solution {
public int minSubArrayLen(int s, int[] nums) {
int sum = 0;
int minLength = nums.length;
boolean flag = false;
for(int left = 0, right = 0; left < nums.length; ++left) {
for(;right < nums.length && sum + nums[right] < s; ++right) {
sum += nums[right];
}
if(right < nums.length && sum + nums[right] >= s) {
flag = true;
minLength = Math.min(minLength, right - left + 1);
}
sum -= nums[left];
}
if(flag) {
return minLength;
}
return 0;
}
}
Take the right as base,
class Solution {
public int minSubArrayLen(int s, int[] nums) {
int minLength = nums.length;
boolean flag = false;
int sum = 0;
for(int left = 0, right = 0; right < nums.length; ++right) {
sum += nums[right];
while(sum >= s) {
flag = true;
minLength = Math.min(minLength, right - left + 1);
sum -= nums[left];
++left;
}
}
if(!flag) {
return 0;
}
return minLength;
}
}
Idea 2. Binary search and Cumulative sum for prefix subarray, similar to Subarray Product Less Than K LT713, for each index i, find the smallest right index such that prefix[right] - prefix[i-1] >= s.
class Solution {
private int findIndex(int[] prefix, int left, int right, int s) {
int i = left, j = right;
while(i < j) {
int mid = i + (j - i)/2;
if(prefix[mid] - prefix[left-1] >= s) j = mid;
else i = mid + 1;
}
return i;
}
public int minSubArrayLen(int s, int[] nums) {
int[] prefix = new int[nums.length + 1];
for(int i = 1; i < prefix.length; ++i) {
prefix[i] = prefix[i-1] + nums[i-1];
}
boolean flag = false;
int minLength = nums.length;
for(int i = 1; i < prefix.length; ++i) {
int smallestIndex = findIndex(prefix, i, prefix.length, s);
if(smallestIndex == prefix.length) {
break;
}
else {
flag = true;
minLength = Math.min(minLength, smallestIndex - i + 1);
}
}
if(!flag) {
return 0;
}
return minLength;
}
}
最新文章
- 虚拟机VMWARE上ORACLE License 的计算
- java设计模式（四）--单例模式
- JavaScript（五）——插入地图
- my_strcmp()
- DataTable过滤重复字段
- 解决IE上登陆oracle OEM时报：“证书错误，导航已阻止”的错误
- (转) IPv6相关RFC
- WCF再学习小结
- js清空前后空格
- haskell入门
- hdu 1595 find the longest of the shortest
- HTML5学习摘录
- Linq to SQL 简单的增删改操作
- Android播放在线音乐文件
- spring的优缺点
- JQuery 的遍历方法 $.each
- [pycocotools修改]cocoeval.py
- 早上STO单紧急寻源处理
- JDK8 - Function介绍
- 禁用系统的Ctrl+Alt+Left/Right（方向键）