图解LeetCode——209. 长度最小的子数组

爪哇缪斯

发布于 2023-09-06 13:42:11

1590

发布于 2023-09-06 13:42:11

文章被收录于专栏：爪哇缪斯

一、题目

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

二、示例

2.1> 示例 1：

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

2.2> 示例 2：

【输入】target = 4, nums = [1,4,4] 【输出】1

2.3> 示例 3：

【输入】target = 11, nums = [1,1,1,1,1,1,1,1] 【输出】0

提示：

1 <= target <= 10^9
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^5

三、解题思路

根据题目描述我们要找出该数组中满足其和大于等于target的长度最小的连续子数组。那么对于“连续子数组”这个关键点，我们很容易就会想到能否采用滑动窗口来解决这道题。

而题目中的另一个关键点——连续子数组其和需要大于等于target，那么就可以理解为变化窗口大小的依据了，具体规则如下所示：

【规则1】如果连续子数组其和 大于等于 target，则扩大窗口的右侧部分；【规则2】如果连续子数组其和小于 target，则缩小窗口的左侧部分；

随着遍历结束，我们返回满足上述条件中最小长度即可；在解题过程中，我们可以采用双指针的方式来模拟滑动窗口。那么以上就是本题的解题思路了，为了便于大家理解，我们一下以输入 target = 7, nums = [2,3,1,2,4,3]为例，看一下具体的操作流程是怎么样的。具体请见下图所示：

四、代码实现

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int i = 0, j = 0, sum = nums[0], result = 100001;
        while(true) {
            if (sum < target) {
                if (j >= nums.length - 1) break;
                sum += nums[++j]; // 向右移动右指针
            } else {
                result = Math.min(result, j - i + 1); 
                sum -= nums[i++]; // 向右移动左指针
            }
        }
        return result == 100001 ? 0 : result;
    }
}