Version: Next

209. 长度最小的子数组

难度 中等

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例：

输入：s = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

进阶：

  • 如果你已经完成了 O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。

209. Minimum Size Subarray Sum

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).

暴力解法

  • 用变量widht记录窗口的宽度，最小为1
  • 利用width计算构成窗口的左右指针left和right
  • 利用滑动窗口法，求窗口内元素的和，一旦达到目标值，立刻返回窗口宽度width即可
  • 依次增加窗口宽度width
  • 宽度width已经加的比数组长度还大了，还没得到子数组，则返回0
public int minSubArrayLen(int s, int[] nums) {
if (nums == null || nums.length == 0) return 0;
int width = 1;
while (width <= nums.length) {
int sum = 0;
int left = 0;
int right = left + width - 1;
while (right < nums.length) {
if (left == 0) {
for (int i = left; i <= right; i++)
sum += nums[i];
} else { // 滑动窗口
sum = sum - nums[left - 1] + nums[right];
}
if (sum >= s) return width;
left++;
right++;
}
width++;
}
return 0;
}
执行结果：
通过
显示详情
执行用时：122 ms, 在所有 Java 提交中击败了18.89%的用户
内存消耗：38.7 MB, 在所有 Java 提交中击败了40.05%的用户

滑动窗口法

  • 定义左右指针left和right形成窗口，同时指向数组的第一个元素

  • 查看当前窗口中元素的和，与s进行比较和比s小：扩大窗口，令right++，直到和 ≥ s大，记录此时窗口的长度

image-20201206200800672

  • 固定right，右移left一步，窗口缩小，重复上一步
  • 直到right无法再移动，返回当时最小子长度

image-20201206200903603

image-20201206201530832

时间复杂度O(N)
public int minSubArrayLen(int s, int[] nums) {
if (nums == null || nums.length == 0) return 0;
int result = nums.length + 1; // 弄一个理论上达不到的最大值，然后逐步缩小它
int left = 0;
int right = 0;
int windowSum = 0; // 窗口中元素的和
while (right < nums.length) { // 只要right还能向右移动
windowSum += nums[right];
while (windowSum >= s) { // 如果此时窗口和，达到了目标值，开始从左侧缩小窗口
// 记录当前最小窗口大小
result = Math.min((right - left + 1), result);
// 移除左侧元素
windowSum -= nums[left];
// left向右移动缩小窗口
left++;
}
right++; // 窗口和没达到目标值，右移right
}
// 如果等于nums.length + 1说明没找到最小子数组，否则就是找到了
return result == nums.length + 1 ? 0 : result;
}
执行结果：
通过
显示详情
执行用时：2 ms, 在所有 Java 提交中击败了85.30%的用户
内存消耗：38.8 MB, 在所有 Java 提交中击败了37.21%的用户