209、长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的连续子数组，返回 0。
示例:
输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。
进阶:
如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。
链接：https://leetcode-cn.com/problems/minimum-size-subarray-sum
题解
理想的最小值为1。
1、前缀和 + 双指针
class Solution {
public int minSubArrayLen(int s, int[] nums) {
int len = nums.length;
int[] profix = new int[len + 1];
profix[0] = 0;
// profix[i] 表示nums[0:i-1]的和
for (int i = 1;i < len+1;i++) {
profix[i] += profix[i-1] + nums[i-1];
}
// System.out.println("profix = " + Arrays.toString(profix));
int l = 0,r = 1;
int min = len + 1;
while(l < r && r < len + 1) {
if(profix[r] - profix[l] < s) {
r++;
} else {
if (min > r - l + 1){
min = r - l + 1;
}
while (l < r && profix[r] - profix[l] >= s) {
l++;
if (min > r - l + 1){
min = r - l + 1;
}
}
}
}
return min == len + 1 ? 0 : min;
}
}
// 不用前缀和
class Solution {
public int minSubArrayLen(int s, int[] nums) {
int n = nums.length;
if (n == 0) {
return 0;
}
int ans = Integer.MAX_VALUE;
int start = 0, end = 0;
int sum = 0;
while (end < n) {
sum += nums[end];
while (sum >= s) {
ans = Math.min(ans, end - start + 1);
sum -= nums[start];
start++;
}
end++;
}
return ans == Integer.MAX_VALUE ? 0 : ans;
}
}
// 作者：LeetCode-Solution
// 链接：https://leetcode-cn.com/problems/minimum-size-subarray-sum/solution/chang-du-zui-xiao-de-zi-shu-zu-by-leetcode-solutio/
2、前缀和+二分查找
class Solution {
public int minSubArrayLen(int s, int[] nums) {
int n = nums.length;
if (n == 0) {
return 0;
}
int ans = Integer.MAX_VALUE;
int[] sums = new int[n + 1];
// 为了方便计算，令 size = n + 1
// sums[0] = 0 意味着前 0 个元素的前缀和为 0
// sums[1] = A[0] 前 1 个元素的前缀和为 A[0]
// 以此类推
for (int i = 1; i <= n; i++) {
sums[i] = sums[i - 1] + nums[i - 1];
}
for (int i = 1; i <= n; i++) {
int target = s + sums[i - 1];
int bound = Arrays.binarySearch(sums, target);
if (bound < 0) {
bound = -bound - 1;
}
if (bound <= n) {
ans = Math.min(ans, bound - (i - 1));
}
}
return ans == Integer.MAX_VALUE ? 0 : ans;
}
}
// 作者：LeetCode-Solution
// 链接：https://leetcode-cn.com/problems/minimum-size-subarray-sum/solution/chang-du-zui-xiao-de-zi-shu-zu-by-leetcode-solutio/
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
