专栏名称: 吴师兄学算法
和程序员小吴一起从初学者的角度学习算法,以动画的形式呈现解题的思路。每周四篇原创文章,期待你的鉴赏!
目录
相关文章推荐
三峡小微  ·  三峡集团启动党组第四轮巡视工作 ·  11 小时前  
三峡小微  ·  三峡集团党组巡视工作领导小组召开2025年第 ... ·  11 小时前  
51好读  ›  专栏  ›  吴师兄学算法

字节跳动高频题,考过 40 次!

吴师兄学算法  · 公众号  ·  · 2022-06-29 20:45

正文

大家好,我是吴师兄,欢迎再次来到「 画解 LeetCode 高频面试 300 题 」系列

今天的题目来源于 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[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[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






请到「今天看啥」查看全文