"/>
·设为首页收藏本站📧邮箱修改🎁免费下载专区💎积分✅卡密📒收藏夹👽聊天室
DZ插件网 门户 站长圈 查看内容

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

2022-7-24 07:20| 发布者: admin| 查看: 314| 评论: 0|原作者: 脚本之家

摘要: 关注“脚本之家”,与百万开发者在一起出处:吴师兄学算法(ID:CXYxiaowu)如若转载请联系原公众号今天的题目来源于LeetCode...
 关注
脚本之家
,与百万开发者在一起

出处:吴师兄学算法(ID:CXYxiaowu)

如若转载请联系原公众号

今天的题目来源于 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 = 11nums = [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行代码搞定最大子数组和问题

面试必会的算法题——求加法

微软一面算法题:反转二叉树

每日打卡赢积分兑换书籍入口



上一篇:通达OA任意用户登录漏洞复现
下一篇:干货|HTML英文单词汇总(PHP新手收藏)

鲜花

握手

雷人

路过

鸡蛋

评论

您需要登录后才可以发表言论 登录立即注册
创宇盾启航版免费网站防御网站加速服务
投诉/建议联系

discuzaddons@vip.qq.com

未经授权禁止转载,复制和建立镜像,
如有违反,按照公告处理!!!
  • 联系QQ客服
  • 添加微信客服

联系DZ插件网微信客服|最近更新|Archiver|手机版|小黑屋|DZ插件网! ( 鄂ICP备20010621号-1 )|网站地图 知道创宇云防御

您的IP:13.58.61.176,GMT+8, 2024-12-25 11:03 , Processed in 0.158192 second(s), 47 queries , Gzip On, Redis On.

Powered by Discuz! X5.0 Licensed

© 2001-2024 Discuz! Team.

关灯
扫一扫添加微信客服
QQ客服返回顶部
返回顶部