【算法优选】 滑动窗口专题——壹

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

😎前言

基本概念

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

分类:窗口有两类,一种是固定大小类的窗口,一类是大小动态变化的窗口。

🍀长度最小的子数组

🚩题目描述:

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

class Solution {
    public int minSubArrayLen(int target, int[] nums) {

    }
}

🚩算法思路:

由于此问题分析的对象是「⼀段连续的区间」,因此可以考虑「滑动窗⼝」的思想来解决这道题。

让滑动窗⼝满⾜:从 i 位置开始,窗⼝内所有元素的和⼩于 target (那么当窗内元素之和第⼀次⼤于等于⽬标值的时候,就是 i 位置开始,满⾜条件的最⼩⻓度)。

做法:将右端元素划⼊窗⼝中,统计出此时窗⼝内元素的和:

  • 如果窗⼝内元素之和⼤于等于 target :更新结果,并且将左端元素划出去的同时继续判断是否满⾜条件并更新结果(因为左端元素可能很⼩,划出去之后依旧满⾜条件)

  • 如果窗⼝内元素之和不满⾜条件: right++ ,另下⼀个元素进⼊窗⼝。

🚩滑动窗口可以解决问题的原因?

为何滑动窗⼝可以解决问题,并且时间复杂度更低?

  • 这个窗⼝寻找的是:以当前窗⼝最左侧元素(记为 left1 )为基准,符合条件的情况。也就是在这道题中,从 left1 开始,满⾜区间和 sum >= target 时的最右侧(记为right1 )能到哪⾥。
  • 我们既然已经找到从 left1 开始的最优的区间,那么就可以⼤胆舍去 left1 。但是如果继续像⽅法⼀⼀样,重新开始统计第⼆个元素( left2 )往后的和,势必会有⼤量重复的计算(因为我们在求第⼀段区间的时候,已经算出很多元素的和了,这些和是可以在计算下次区间和的时候⽤上的)。
  • 此时, rigth1 的作⽤就体现出来了,我们只需将 left1 这个值从sum 中剔除。从right1 这个元素开始,往后找满⾜ left2 元素的区间(此时 right1 也有可能是满⾜的,因为 left1 可能很⼩。 sum 剔除掉 left1 之后,依旧满⾜⼤于等于target )。这样我们就能省掉⼤量重复的计算。

这样我们不仅能解决问题,⽽且效率也会⼤⼤提升。时间复杂度:虽然代码是两层循环,但是我们的 left 指针和 right 指针都是不回退的,两者最多都往后移动 n 次。因此时间复杂度是O(N)

🚩代码实现:

class Solution {
    public int minSubArrayLen(int target, int[] nums)
    {
        int n = nums.length;
        int sum = 0;
        int len = Integer.MAX_VALUE;
        for(int left = 0, right = 0; right < n; right++) {
            sum += nums[right]; // 进窗⼝
            // 判断
            while(sum >= target) {
                len = Math.min(len, right - left + 1); // 更新结果
                sum -= nums[left++]; // 出窗⼝
            }
        }
        return len == Integer.MAX_VALUE ? 0 : len;
    }
}

🌲无重复字符的最长子串

🚩题目描述:

给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。

  • 示例 1:
    输入: s = “abcabcbb”
    输出: 3
    解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。

  • 示例 2:
    输入: s = “bbbbb”
    输出: 1
    解释: 因为无重复字符的最长子串是 “b”,所以其长度为 1。

  • 示例 3:
    输入: s = “pwwkew”
    输出: 3
    解释: 因为无重复字符的最长子串是 “wke”,所以其长度为 3。请注意,你的答案必须是 子串 的长度,“pwke” 是一个子序列,不是子串。

class Solution {
    public int lengthOfLongestSubstring(String s) {

    }
}

🚩算法思路:

研究的对象依旧是⼀段连续的区间,因此继续使⽤「滑动窗⼝」思想来优化。

让滑动窗⼝满⾜:窗⼝内所有元素都是不重复的。

做法:右端元素 ch 进⼊窗⼝的时候,哈希表统计这个字符的频次:

  • 如果这个字符出现的频次超过 1 ,说明窗⼝内有重复元素,那么就从左侧开始划出窗⼝,
    直到 ch 这个元素的频次变为 1 ,然后再更新结果。
  • 如果没有超过 1 ,说明当前窗⼝没有重复元素,可以直接更新结果

🚩代码实现:

class Solution {
    public int lengthOfLongestSubstring(String ss) {
        char[] s = ss.toCharArray();
        int[] hash = new int[128]; // ⽤数组模拟哈希表
        int left = 0;
        int right = 0;
        int n = ss.length();
        int ret = 0;
        while(right < n) {
            hash[s[right]]++; // 进⼊窗⼝
            // 判断
            while(hash[s[right]] > 1) {
                hash[s[left++]]--; // 出窗⼝
            }
            ret = Math.max(ret, right - left + 1); // 更新结果
            right++; // 让下⼀个字符进⼊窗⼝
        }
        return ret;
    }
}

🎍最大连续1的个数|||

🚩题目描述:

给定一个二进制数组 nums 和一个整数 k,如果可以翻转最多 k 个 0 ,则返回 数组中连续 1 的最大个数 。

  • 示例 1:
    输入:nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
    输出:6
    解释:[1,1,1,0,0,1,1,1,1,1,1]
    粗体数字从 0 翻转到 1,最长的子数组长度为 6。
  • 示例 2:
    输入:nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
    输出:10
    解释:[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
    粗体数字从 0 翻转到 1,最长的子数组长度为 10。
class Solution {
    public int longestOnes(int[] nums, int k) {

    }
}

🚩算法思路:

不要去想怎么翻转,不要把问题想的很复杂,这道题的结果⽆⾮就是⼀段连续的 1 中间塞了 k 个 0 嘛。

因此,我们可以把问题转化成:求数组中⼀段最⻓的连续区间,要求这段区间内 0 的个数不超过 k 个。

既然是连续区间,可以考虑使⽤「滑动窗⼝」来解决问题。

算法流程:

  1. 初始化⼀个⼤⼩为 2 的数组就可以当做哈希表 hash 了;初始化⼀些变量 left = 0 ,
    right = 0 , ret = 0 ;
  2. 当 right ⼩于数组⼤⼩的时候,⼀直下列循环:
  • 让当前元素进⼊窗⼝,顺便统计到哈希表中;
  • 检查 0 的个数是否超标:

如果超标,依次让左侧元素滑出窗⼝,顺便更新哈希表的值,直到 0 的个数恢复正
常;

  • 程序到这⾥,说明窗⼝内元素是符合要求的,更新结果;
  • right++ ,处理下⼀个元素;
  1. 循环结束后, ret 存的就是最终结果

🚩代码实现:

class Solution {
    public int longestOnes(int[] nums, int k) {
        int ret = 0;
        for(int left = 0, right = 0, zero = 0; right < nums.length; right++) {
            if(nums[right] == 0) {
                zero++; // 进窗⼝
            }
            while(zero > k) {
                // 判断
                if(nums[left++] == 0) {
                    zero--; // 出窗⼝
                }
            }
            ret = Math.max(ret, right - left + 1); // 更新结果
        }
        return ret;
    }
}

🎋将x减到0的最小操作数

🚩题目描述:

给你一个整数数组 nums 和一个整数 x 。每一次操作时,你应当移除数组 nums 最左边或最右边的元素,然后从 x 中减去该元素的值。请注意,需要 修改 数组以供接下来的操作使用。

如果可以将 x 恰好 减到 0 ,返回 最小操作数 ;否则,返回 -1 。

  • 示例 1:
    输入:nums = [1,1,4,2,3], x = 5
    输出:2
    解释:最佳解决方案是移除后两个元素,将 x 减到 0 。

  • 示例 2:
    输入:nums = [5,6,7,8,9], x = 4
    输出:-1

  • 示例 3:
    输入:nums = [3,2,20,1,1,3], x = 10
    输出:5
    解释:最佳解决方案是移除后三个元素和前两个元素(总共 5 次操作),将 x 减到 0 。

class Solution {
    public int minOperations(int[] nums, int x) {

    }
}

🚩算法思路:

题⽬要求的是数组「左端+右端」两段连续的、和为 x 的最短数组,信息量稍微多⼀些,不易理清思路;我们可以转化成求数组内⼀段连续的、和为 sum(nums) - x 的最⻓数组。此时,就是熟悉的「滑动窗⼝」问题了

🚩算法流程:

  1. 转化问题:求 target = sum(nums) - x 。如果 target < 0 ,问题⽆解;
  2. 初始化左右指针 left = 0 , right = 0 (滑动窗⼝区间表⽰为 [left, right) ,左右区间是否开闭很重要,必须设定与代码⼀致),记录当前滑动窗⼝内数组和的变量 sum = 0 ,记录当前满⾜条件数组的最⼤区间⻓度 maxLen = -1 ;
  3. 当 right ⼩于等于数组⻓度时,⼀直循环:
  • 如果 sum < target ,右移右指针,直⾄变量和⼤于等于 target ,或右指针已经移到
    头;
  • 如果 sum > target ,右移左指针,直⾄变量和⼩于等于 target ,或左指针已经移到
    头;
  • 如果经过前两步的左右移动使得 sum == target ,维护满⾜条件数组的最⼤⻓度,并
    让下个元素进⼊窗⼝;
  1. 循环结束后,如果 maxLen 的值有意义,则计算结果返回;否则,返回 -1 。

🚩代码实现:

class Solution {
    public int minOperations(int[] nums, int x) {
        int sum = 0;
        for(int a : nums) {
            sum += a;
        }
        int target = sum - x;
        // 处理细节
        if(target < 0) {
            return -1;
        }
        int ret = -1;
        for(int left = 0, right = 0, tmp = 0; right < nums.length; right++) {
            tmp += nums[right]; // 进窗⼝
            // 判断
            while(tmp > target) {
                tmp -= nums[left++]; // 出窗⼝
            }
            if(tmp == target){
                ret = Math.max(ret, right - left + 1); // 更新结果
            }
        }
        if(ret == -1) {
            return ret;
        } else {
            return nums.length - ret;
        }
    }
}

⭕总结

关于《【算法优选】 滑动窗口专题——壹》就讲解到这儿,感谢大家的支持,欢迎各位留言交流以及批评指正,如果文章对您有帮助或者觉得作者写的还不错可以点一下关注,点赞,收藏支持一下!一起加油文章来源地址https://www.toymoban.com/news/detail-714232.html

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

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

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

相关文章

  • 【算法专题】滑动窗口

    题目链接 - Leetcode -209.长度最小的子数组 Leetcode -209.长度最小的子数组 题目:给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组[numsl, numsl + 1, …, numsr - 1, numsr] ,并返回其长度。 如果不存在符合条件的子数组,返

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

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

    2024年02月07日
    浏览(52)
  • 【算法专题突破】滑动窗口 - 长度最小的子数组(9)

    目录 1. 题目解析 2. 算法原理 3. 代码编写 写在最后: 题目链接:209. 长度最小的子数组 - 力扣(Leetcode)  要注意的是,题目给的是正整数, 而题目要求并不难理解,就是找最短的子数组。 如果使用暴力的话,就是一个O(N3)的算法,复杂度很高, 我们可以用滑动窗口来做,

    2024年02月09日
    浏览(32)
  • 力扣精选算法100题——水果成篮(滑动窗口专题)

    本题链接👉水果成篮 我就按照实例1来进行对这题的理解。 1代表种类类型,这个数组里面有2个种类类型 ps:种类1和种类2 ,只不过种类1是有2个水果,种类2有一个水果,共计3个水果。 本题需要解答:收集水果的最大数目. 但是前提条件: 我们只有2个篮子,每个篮子里只能装

    2024年01月17日
    浏览(41)
  • 力扣精选算法100题——找到字符串中所有字母异位词(滑动窗口专题)

    本题链接👉找到字符串中所有字母异位词 给定2个字符串s和p,找到s中所有p的变位词的字串,就是p是\\\"abc\\\",在s串中找到与p串相等的字串,可以位置不同,但是字母必须相同,比如”bca\\\",\\\"bac\\\"等,都是可以被称之为变位词。最终返回与p串字母相等但排列不同的字符串的初始索引

    2024年01月19日
    浏览(67)
  • 【算法优选】双指针专题——贰

    常⻅的双指针有两种形式,⼀种是 对撞指针 ,⼀种是 左右指针 对撞指针 :⼀般⽤于顺序结构中,也称左右指针。 对撞指针从两端向中间移动。⼀个指针从最左端开始,另⼀个从最右端开始,然后逐渐往中间逼近。 对撞指针的终⽌条件⼀般是两个指针相遇或者错开(也可能

    2024年02月08日
    浏览(52)
  • 【算法优选】前缀和专题——叁

    含义 : 前缀和实际上就是对于长度为n的数组, 我们新建立一个数组长度为n+1,第i个元素的值为前i个元素的和(包括第i个元素) 。 特点 : 前缀和数组比原数组多一个长度。 前缀和的第0个元素的值为0。 根据前缀和数组的特点,求前缀和时。我们只需要用第i个元素的值

    2024年02月06日
    浏览(44)
  • 【算法优选】 前缀和专题——壹

    含义 : 前缀和实际上就是对于长度为n的数组, 我们新建立一个数组长度为n+1,第i个元素的值为前i个元素的和(包括第i个元素) 。 特点 : 前缀和数组比原数组多一个长度。 前缀和的第0个元素的值为0。 根据前缀和数组的特点,求前缀和时。我们只需要用第i个元素的值

    2024年02月08日
    浏览(39)
  • 【算法优选】双指针专题——壹

    常⻅的双指针有两种形式,⼀种是 对撞指针 ,⼀种是 左右指针 对撞指针 :⼀般⽤于顺序结构中,也称左右指针。 对撞指针从两端向中间移动。⼀个指针从最左端开始,另⼀个从最右端开始,然后逐渐往中间逼近。 对撞指针的终⽌条件⼀般是两个指针相遇或者错开(也可能

    2024年02月08日
    浏览(47)
  • 【算法优选】双指针专题——叁

    常⻅的双指针有两种形式,⼀种是 对撞指针 ,⼀种是 左右指针 对撞指针 :⼀般⽤于顺序结构中,也称左右指针。 对撞指针从两端向中间移动。⼀个指针从最左端开始,另⼀个从最右端开始,然后逐渐往中间逼近。 对撞指针的终⽌条件⼀般是两个指针相遇或者错开(也可能

    2024年02月08日
    浏览(46)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包