【算法|数组】滑动窗口

这篇具有很好参考价值的文章主要介绍了【算法|数组】滑动窗口。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

算法|数组——滑动窗口

引入

给定一个含有 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

解法

暴力解法

【算法|数组】滑动窗口,数据结构与算法,算法,数据结构,leetcode

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int result = Integer.MAX_VALUE;
        for(int i = 0; i < nums.length; i++){
            int sum = 0;
            for(int j = i; j < nums.length; j++){
                sum += nums[j];
                if(sum >= target){
                    result = Math.min(result,j - i + 1);
                    break;
                }
            }
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}

这种做法可以很容易想到,可是谁想到它…

【算法|数组】滑动窗口,数据结构与算法,算法,数据结构,leetcode

超时了哈哈😓😓😓😓😓😓😓😓


那么下面我们看看另外一种思路。

滑动窗口

先看示例代码:

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int result = Integer.MAX_VALUE;
        int i = 0;
        int sum = 0;
        int length = 0;
        for(int j = 0; j < nums.length; j++){
            sum += nums[j];
            while(sum >= target){
                length = j - i + 1;
                result = Math.min(result,length);
                sum -= nums[i++];
            }
        }
 
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}

下面见分析:

【算法|数组】滑动窗口,数据结构与算法,算法,数据结构,leetcode

还不错吧😊😊😊😼

【算法|数组】滑动窗口,数据结构与算法,算法,数据结构,leetcode


至此先不更个1-2天,哥们要考科四,现在一题都没看,再不看就寄了😥😥😥😥文章来源地址https://www.toymoban.com/news/detail-659090.html

到了这里,关于【算法|数组】滑动窗口的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构与算法之数组: Leetcode 914. 卡牌分组 (Typescript版)

    卡牌分组 https://leetcode.cn/problems/x-of-a-kind-in-a-deck-of-cards/ 描述 给定一副牌,每张牌上都写着一个整数。 此时,你需要选定一个数字 X,使我们可以将整副牌按下述规则分成 1 组或更多组: 每组都有 X 张牌。 组内所有的牌上都写着相同的整数。 仅当你可选的 X = 2 时返回 true。

    2024年02月02日
    浏览(42)
  • java数据结构与算法刷题-----LeetCode209. 长度最小的子数组

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 代码:时间复杂度O(n).空间复杂度O(1)

    2024年01月21日
    浏览(54)
  • 数据结构与算法之堆: Leetcode 215. 数组中的第K个最大元素 (Typescript版)

    数组中的第K个最大元素 https://leetcode.cn/problems/kth-largest-element-in-an-array/ 描述 给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。 请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。 你必须设计并实现时间复杂度为 O(n) 的算法解决此

    2024年02月07日
    浏览(53)
  • 【算法|数组】滑动窗口

    给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度**。**如果不存在符合条件的子数组,返回 0 。 示例 1: 示例 2: 示例 3: 暴力解法 这种做法可以很容易想到,可是谁

    2024年02月12日
    浏览(39)
  • 【Leetcode刷题-Python/C++】长度最小的子数组(滑动窗口)

    209.长度最小的子数组 给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。 输入:target = 7, nums = [2,3,1,2,4,3] 输出:2 解释:子数

    2023年04月08日
    浏览(41)
  • LeetCode算法小抄--滑动窗口算法

    ⚠申明: 未经许可,禁止以任何形式转载,若要引用,请标注链接地址。 全文共计6244字,阅读大概需要3分钟 🌈更多学习内容, 欢迎👏关注👀文末我的个人微信公众号:不懂开发的程序猿 个人网站:https://jerry-jy.co/ 滑动窗口算法 思路 1、我们在字符串 S 中使用双指针中的

    2023年04月09日
    浏览(40)
  • LeetCode 2090. K Radius Subarray Averages【前缀和,滑动窗口,数组】中等

    本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,

    2024年02月11日
    浏览(48)
  • LeetCode 1493. 删掉一个元素以后全为 1 的最长子数组 - 二分 + 滑动窗口

    删掉一个元素以后全为 1 的最长子数组 提示 中等 90 相关企业 给你一个二进制数组 nums ,你需要从中删掉一个元素。 请你在删掉元素的结果数组中,返回最长的且只包含 1 的非空子数组的长度。 如果不存在这样的子数组,请返回 0 。 提示 1: 输入:nums = [1,1,0,1] 输出:3 解

    2024年02月17日
    浏览(42)
  • 【LeetCode 算法专题突破】滑动窗口(⭐)

    学完了双指针算法,滑动窗口那肯定是逃不掉了,我个人感觉他俩就不分家,不把滑动窗口的题目好好刷上一刷我都难受 先来一道经典的滑动窗口试试水 题目链接:209. 长度最小的子数组 其实滑动窗口题目的解法都大同小异,我们基本上写几道题目,就能很好的掌握这个算

    2024年02月07日
    浏览(53)
  • Java【手撕滑动窗口】LeetCode 209. “长度最小子数组“, 图文详解思路分析 + 代码

    各位读者好, 我是小陈, 这是我的个人主页, 希望我的专栏能够帮助到你: 📕 JavaSE基础: 基础语法, 类和对象, 封装继承多态, 接口, 综合小练习图书管理系统等 📗 Java数据结构: 顺序表, 链表, 堆, 二叉树, 二叉搜索树, 哈希表等 📘 JavaEE初阶: 多线程, 网络编程, TCP/IP协议, HTTP协议

    2024年02月11日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包