长度最小的子数组（Java详解）

柔光的暖阳◎ 2024-02-05 11:21 15阅读 0赞

**目录**

题目描述

题解

思路分析

暴力枚举代码

滑动窗口代码

--------------------

## 题目描述 ##

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

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

**示例：**

>     输入：target = 7, nums = [2,3,1,2,4,3]
>     输出：2

>     输入：target = 4, nums = [1,4,4]
>     输出：1

## **题解** ##

### **思路分析** ###

题目要求我们找到**和 >= target** 的 **最小** 且 **连续** 的子数组，我们很容易想到**暴力枚举**的方法，即访问数组的每一个元素i，并将i作为第一个元素，向后寻找

![ed8305e16ee84c2b8cbbe8b55c96e38a.png][]

### **暴力枚举代码** ###

class Solution {
        public int minSubArrayLen(int target, int[] nums) {
            int count = 0;
            for(int i = 0; i < nums.length; i++){
                int sum = 0;
                //向后遍历找到以nums[i]为起始元素的最小数组
                for(int j = i; j < nums.length;j++){
                    sum += nums[j];
                    if(sum >= target){
                         //更新目标值 由于count的初始值为0，因此需要更新初始值，
                         //否则最小值恒为0
                        if(count > j-i+1 || count == 0){
                            count = j-i+1;
                        }
                        break;
                    }
                }
            }
            //若count未被更新，则返回0，即没有子数组的和大于target，
            //若count被跟新，则返回最小的子数组长度
            return count;
        }
    }

此时我们通过遍历访问了数组的每个元素，在访问每个元素时，以该元素为起始元素，并向后寻找其最小长度的子数组，因此**时间复制度**为O(![^\{\_N\{2\}\}][N_2])

而，题目所给的数组中所有元素**均是正整数**，因此每加上一个元素，子数组的和 sum 增加，通过这个特性，我们可以想到使用滑动窗口来解决这个问题

> **什么是滑动窗口？**

滑动窗口是一种基于**双指针**的思想，两个指针指向的元素之间形成了一个窗口

因此滑动窗口是通过两个指针来维护的，那么如何移动这两个指针，是使用滑动窗口解决问题的关键

![3b1b1bdc64d642ed940472d796bd16cd.png][]

初始时，两个指针都指向0下标位置

![0a37b5c8088d47ceb0de3eb4e8e19f2b.png][]

遍历元素，若**条件不满足**，则将right指针向右移动，直到条件满足为止

![4b562d70e1654432bebda7f93bf41855.png][]

当**条件满足**时，则保持右指针不变，开始移动左指针 left

![44b0bbb34f134b128ea496d3b878b851.png][]

在向窗口中添加新元素或从窗口中删除旧元素时，可能会更新一些与窗口范围有关的数据（例如，本题就需要更新最小子数组的长度）

> **如何使用滑动窗口解决本题？**

（1）我们定义两个指针left right，并让其都指向数组首元素

![e0ef9c0e6c794a4797d3b41f5327740b.png][]

（2）此时窗口内只有 2 这一个元素，不满足和 sum >= target，因此将right向右移动，将新的元素加入窗口中，并判断此时子数组的和 sum 是否大于等于target，若满足，则不再移动right

![84ba4f85ae214b86b9d96f19b2e8811f.png][]

（3）在sum >= target时，首先判断最小的子数组长度是否需要更新，并保持right不变，向右移动左指针left，删除旧的元素，直到sum < target

![fceb53b22e1b439fa11b7336307ab8cd.png][]

（4）循环（2）（3），直到right遍历完数组

> **为什么可以使用滑动窗口解决本题？**  
>

因为我们要找的子数组是**连续的，**且数组中的元素都为正整数，即子数组中增加一个元素，子数组中的元素和sum增加，从窗口中删除一个元素，sum减小，因此我们可以通过改变子数组的两端元素来更新数组，因此可以使用滑动窗口来解决本题

由于左右指针都只遍历了一遍数组，因此**时间复杂度**为**O(N)**

### **滑动窗口代码** ###

class Solution {
        public int minSubArrayLen(int target, int[] nums) {
            int left = 0;
            int right = 0;
            int sum = nums[0];
            int len = nums.length;
            int count = 0;
            while(left <= right && right < len){
                //小于目标值，向右移动右指针right
                while(left <= right && right < len && sum < target){
                    right++;
                    if(right == len){
                        break;
                    }
                    sum += nums[right];
                }
                //大于等于目标值
                while(left <= right && sum >= target){
                    //更新目标值 由于count的初始值为0，因此需要更新初始值，否则最小值恒为0
                    if((right - left) < count || count == 0){
                        count = right - left + 1;
                    }
                    //左边值出窗口，left向右移动
                    sum -= nums[left];
                    left++;
                }
            }
            //若count未被更新，则返回0，即没有子数组的和大于target，
            //若count被跟新，则返回最小的子数组长度
            return count;
        }
    }

**题目来自：**

[LCR 008. 长度最小的子数组 - 力扣（LeetCode）][LCR 008. _ - _LeetCode]

[ed8305e16ee84c2b8cbbe8b55c96e38a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/9bce2ec61d8f48f19b5050bce956edbf.png
[N_2]: https://latex.csdn.net/eq?%5E%7B_N%7B2%7D%7D
[3b1b1bdc64d642ed940472d796bd16cd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/dc2a0660b0e14adf84ceb2c1c9ef3f36.png
[0a37b5c8088d47ceb0de3eb4e8e19f2b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/1f99689b97f542358f57ff3bcf8f9b2b.png
[4b562d70e1654432bebda7f93bf41855.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/5bbc8193f2ff4155bf04a764fa741142.png
[44b0bbb34f134b128ea496d3b878b851.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/a9270637914e4ae3808f5df55a7db67e.png
[e0ef9c0e6c794a4797d3b41f5327740b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/0aa09df0c1304ae9a949bc3bffa16aee.png
[84ba4f85ae214b86b9d96f19b2e8811f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/802cf14dbabb42acac3a0b07d17dcda2.png
[fceb53b22e1b439fa11b7336307ab8cd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/aee3cffb451c459d9d4365d3ba65273c.png
[LCR 008. _ - _LeetCode]: https://leetcode.cn/problems/2VG8Kg/description/