【C++速刷精品】滑动窗口

2023-12-19 01:57:29

【C++速刷精品】滑动窗口

一、长度最小的子数组

1、题目链接

leetcode链接

在这里插入图片描述

2、题目解析

讲解一下什么是滑动窗口？
滑动窗口就是一个同向双指针利用单调性的两个指针区间为窗口，right指针往右移动则是入窗口，left指针往右移动则是出窗口，我们用的步骤如下图：
在这里插入图片描述
在这里插入图片描述

3、代码

在这里插入图片描述

二、无重复字符的最长字串

1、题目链接

leetcode链接
在这里插入图片描述

2、题目解析

构造一个hash函数表，将right和left从0开始，不断的将right的值存入到hash表中，如果发现表中存入了两个了，那么就更新left的值，并进行更新ret。

在这里插入图片描述

3、代码

在这里插入图片描述

三、最大连续1的个数III

1、题目链接

题目链接

在这里插入图片描述

2、题目解析

此时定义一个ret用来记录走过的0的个数，right走过一个0就加加，left走过一个0就减减，我们循环的条件在于：当right指针遇见1的时候，一直往右走直到遇见0，每遇见一个0就将ret进行加加，直到ret的个数比k大的时候就需要出窗口了，也就是我们的left指针往右移动，直到找到0，每遇见一个0就将ret减减再left往右走一步，这个判断跳出条件在于ret<k，而在每次进行这个操作的时候，我们都进行算一下下标，也就是中间有多少个元素，最终等right到最后一个位置的下一个位置的时候，我们就结束。

在这里插入图片描述

3、代码

在这里插入图片描述

四、将x减到0的最小操作数

1、题目链接

leetcode链接

在这里插入图片描述

2、题目解析

在这里插入图片描述

在这里插入图片描述

3、代码

在这里插入图片描述

五、水果成篮

1、题目链接

leetcode链接

在这里插入图片描述

2、题目解析

在这里插入图片描述

3、代码

在这里插入图片描述

六、找到字符串中所有字母异位词

1、题目链接

leetcode链接
在这里插入图片描述

2、题目解析

在这里插入图片描述

3、代码

在这里插入图片描述

七、串联所有单词的字串

1、题目链接

leetcode传送门

在这里插入图片描述

2、题目解析

在这里插入图片描述
在这里插入图片描述

3、代码

在这里插入图片描述

八、最小覆盖字串

1、题目链接

leetcode链接

在这里插入图片描述

2、题目解析

在这里插入图片描述

在这里插入图片描述

3、代码

NO1.利用unordered_map容器来进行解决，但算法复杂度太高
在这里插入图片描述

No2.用hash数组进行解决，算法复杂度低
在这里插入图片描述

文章来源:https://blog.csdn.net/m0_70088010/article/details/135025209
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。