字节跳动高频题,长度最小的子数组

 关注

“脚本之家

”，与百万开发者在一起

今天的题目来源于 LeetCode 第 209 号问题：长度最小的子数组，难度为「中等」，根据 CodeTop 爆料，字节、腾讯、微软都考察过多次。

一、题目描述

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 1 <= target <= 109
• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105

进阶：

• 如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

二、题目解析

很经典的滑动窗口的题目。

具体操作如下：

1、初始化一个滑动窗口，左边界位置为 0，接下来开始设置右边界的位置，通过数组不断的去调整右边界的位置，所以一开始右边界的位置也是 0，如果数组为空，那么这个窗口就不存在；如果数组不为空，那么窗口就是第一个元素。

2、计算此时滑动窗口里面所有元素的值。

3、如果滑动窗口的元素和小于了 target，那么说明还没有找到了一个满足条件的连续子数组，需要继续扩充滑动窗口，扩充的方式就是让右边界向右移动。

4、如果滑动窗口的元素和大于等于了 target，那么说明找到了一个满足条件的连续子数组，计算出这个连续子数组的长度来，把这个结果 result 和之前的保存的结果进行对比取最小值。

5、基于 4 的情况，需要开始尝试缩小滑动窗口，去寻找更短的滑动窗口，缩小的方法就是不断的移动左边界，直到滑动窗口里面的元素和小于了 target 为止，在移动过程中，如果发现滑动窗口的元素和依旧大于等于了 target，继续缩小同时更新 result。

6、最后需要注意一点， 一开始，result 可以初始化为一个超过数组长度的值，这样的目的是为了最后返回结果的时候判断 result 有没有被更新，如果没有被更新，并且滑动窗口的长度不可能为 result，因为超过了数组的长度，那就代表不存在符合条件的子数组，需要返回 0 ，比如 target = 11， nums = [1,1,1,1,1,1,1,1]， 先设置 result = 9，执行完后续代码，result 依旧为 9，代表 nums 里面找不到一个子数组和大于等于 11 ，需要返回 0。

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 长度最小的子数组（LeetCode 209）：https://leetcode.cn/problems/minimum-size-subarray-sum/
class Solution {
    public int minSubArrayLen(int target, int[] nums) {

        // 滑动窗口的左端
        int left = 0;

        // 滑动窗口中所有元素的和
        int sum = 0;

        // 记录滑动窗口的长度，并且不断更新获取最小的那个
        // 一开始，result 可以初始化为一个超过数组长度的值
        // 这样的目的是为了最后返回结果的时候判断 result 有没有被更新
        // 如果没有被更新，并且滑动窗口的长度不可能为 result，因为超过了数组的长度
        // 那就代表不存在符合条件的子数组，需要返回 0 
        // 比如 target = 11, nums = [1,1,1,1,1,1,1,1]
        // 先设置 result = 9，执行完后续代码，result 依旧为 9
        // 代表 nums 里面找不到一个子数组和大于等于 11 ，需要返回 0
        int result = nums.length + 1;
        
        // 滑动窗口的右端从 0 开始，这样，当 nums 为空时，可以直接跳出 for 循环
        for (int right = 0; right < nums.length; right++) {

            // 滑动窗口中加入了 nums[right] 这个元素
            // 滑动窗口元素和需要发生变化
            sum += nums[right];

            // 变化之后需要判断一下，如果滑动窗口的元素和大于等于了 target
            // 那么这个时候就需要不断的向右移动 left，缩小滑动窗口的长度
            while (sum >= target) {
                
                // 在获取到一个满足要求的子数组时，更新 result 的值
                result = Math.min(result, right - left + 1);

                // 把 nums[left] 移除滑动窗口
                sum -= nums[left];

                // 即 left 向右移动
                left++;

            }
        }

        // 返回结果
        return result == nums.length + 1 ? 0 : result;
    }
}

2、C++ 代码

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        // 滑动窗口的左端
        int left = 0;

        // 滑动窗口中所有元素的和
        int sum = 0;

        // 记录滑动窗口的长度，并且不断更新获取最小的那个
        // 一开始，result 可以初始化为一个超过数组长度的值
        // 这样的目的是为了最后返回结果的时候判断 result 有没有被更新
        // 如果没有被更新，并且滑动窗口的长度不可能为 result，因为超过了数组的长度
        // 那就代表不存在符合条件的子数组，需要返回 0 
        // 比如 target = 11, nums = [1,1,1,1,1,1,1,1]
        // 先设置 result = 9，执行完后续代码，result 依旧为 9
        // 代表 nums 里面找不到一个子数组和大于等于 11 ，需要返回 0
        int result = nums.size() + 1;
        
        // 滑动窗口的右端从 0 开始，这样，当 nums 为空时，可以直接跳出 for 循环
        for (int right = 0; right < nums.size(); right++) {

            // 滑动窗口中加入了 nums[right] 这个元素
            // 滑动窗口元素和需要发生变化
            sum += nums[right];

            // 变化之后需要判断一下，如果滑动窗口的元素和大于等于了 target
            // 那么这个时候就需要不断的向右移动 left，缩小滑动窗口的长度
            while (sum >= target) {
                
                // 在获取到一个满足要求的子数组时，更新 result 的值
                result = min(result, right - left + 1);

                // 把 nums[left] 移除滑动窗口
                sum -= nums[left];

                // 即 left 向右移动
                left++;

            }
        }

        // 返回结果
        return result == nums.size() + 1 ? 0 : result;

    }
};

3、Python 代码

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        # 滑动窗口的左端
        left = 0

        # 滑动窗口中所有元素的和
        sum = 0

        # 记录滑动窗口的长度，并且不断更新获取最小的那个
        # 一开始，result 可以初始化为一个超过数组长度的值
        # 这样的目的是为了最后返回结果的时候判断 result 有没有被更新
        # 如果没有被更新，并且滑动窗口的长度不可能为 result，因为超过了数组的长度
        # 那就代表不存在符合条件的子数组，需要返回 0 
        # 比如 target = 11, nums = [1,1,1,1,1,1,1,1]
        # 先设置 result = 9，执行完后续代码，result 依旧为 9
        # 代表 nums 里面找不到一个子数组和大于等于 11 ，需要返回 0
        result = len(nums) + 1
        
        # 滑动窗口的右端从 0 开始，这样，当 nums 为空时，可以直接跳出 for 循环
        for right in range(len(nums)) :

            # 滑动窗口中加入了 nums[right] 这个元素
            # 滑动窗口元素和需要发生变化
            sum += nums[right]

            # 变化之后需要判断一下，如果滑动窗口的元素和大于等于了 target
            # 那么这个时候就需要不断的向右移动 left，缩小滑动窗口的长度
            while sum >= target : 
                
                # 在获取到一个满足要求的子数组时，更新 result 的值
                result = min(result, right - left + 1)

                # 把 nums[left] 移除滑动窗口
                sum -= nums[left]

                # 即 left 向右移动
                left += 1

      
        # 返回结果
        return 0 if result == len(nums) + 1 else result

四、复杂度分析

时间复杂度：O(n)，其中 n 是数组的长度。

空间复杂度：O(1)。

<END>
程序员专属T恤
商品直购链接 👇
  推荐阅读：
这是一件程序员才懂的T恤
动态规划：8行代码搞定最大子数组和问题
面试必会的算法题——求加法
微软一面算法题：反转二叉树
每日打卡赢积分兑换书籍入口