【滑动窗口】算法实战

简介: 滑动窗口算法的原理和leetcode中的相关题目题解。

一、算法原理

滑动窗口,顾名思义,就是有一个大小可变的窗口,左右两端方向一致的向前滑动(右端固定,左端滑动;左端固定,右端滑动)。

image.png

滑动窗口的本质其实也是一种双指针算法,它是根据单调性的思想,使用”同向双指针“,索引字符串或者列表中的一个区间[left,right]

滑动窗口的步骤一般如下所示:

1、在序列中使用双指针中的左右指针技巧,初始化 left = right = 0,把索引闭区间 [left, right] 称为一个窗口。
2、先不断地增加 right 指针扩大窗口 [left, right],直到窗口中的序列符合要求。
3、此时,停止增加 right,转而不断增加 left 指针缩小窗口 [left, right],直到窗口中的序列不再符合要求。同时,每次增加 left前,都要更新一轮结果。
4、重复第 2 和第 3 步,直到 right 到达序列的尽头。


二、算法实战

1. leetcode209 长度最小的子数组

image.png

长度最小的子数组

解题思路:

image.png

代码实现:

class Solution {
   
   
public:
    int minSubArrayLen(int target, vector<int>& nums) {
   
   
        int left = 0, right = left, n = nums.size() - 1;
        int Min = 0, sum = 0;
        while(right <= n)
        {
   
   
            sum += nums[right];
            while(sum >= target)
            {
   
   
                int tmp = right - left + 1;
                Min = Min == 0 ? tmp : min(tmp, Min);
                sum -= nums[left++];
            }
            right++;
        }

        return Min;
    }
};

image.png


2. leetcode3 无重复字符的最长子串

image.png

无重复字符的最长字串

解题思路:滑动窗口+哈希表

题目要求的是无重复字符,为了统计每个字符出现的次数,这里我们可以使用哈希表来统计每个字符出现的次数。

image.png

代码实现:

class Solution {
   
   
public:
    //滑动窗口问题
    int lengthOfLongestSubstring(string s) {
   
   
        int hash[128] = {
   
   0};
        int n = s.size() - 1, len = 0;
        for(int left = 0, right = 0; right <= n; right++)
        {
   
   
            hash[s[right]]++; // 进窗口
            while(hash[s[right]] > 1)
            {
   
   
                hash[s[left]]--;//不满足要求,出窗口,直到满足要求为止
                left++;
            }
            len = max(len, right - left + 1);
        }
        return len;
    }
};

image.png


3. leetcode1004 最大连续1的个数

image.png

最大连续1的个数III

解题思路:

因为数组中除了0就是1,题目要求我们最多只能翻转k个0,求的是翻转k个0后,最长连续1的个数。

我们可以转换一下思路:找出最长的子数组,该子数组中0的个数不超过k个。

image.png

代码实现:

class Solution {
   
   
public:
    int longestOnes(vector<int>& nums, int k) {
   
   
        int n = nums.size();
        int zero = 0, ret = 0;
        for(int left = 0, right = 0; right < n; right++)
        {
   
   
            if(nums[right] == 0)
                zero++;
            while(zero > k)
            {
   
   
                if(nums[left] == 0)
                    zero--;
                left++;
            }
            ret = max(ret, right - left + 1);
        }
        return ret;
    }
};

image.png


4. leetcode1685 将x减到0的最小操作数

image.png

将x减到0的最小操作数

这个题目我们可以进行进一步转化:转换为——> 找出最长的子数组的的长度,所有元素的和正好等于 sum-x,然后再利用滑动窗口解决即可。

代码实现:

class Solution {
   
   
public:
    int minOperations(vector<int>& nums, int x) {
   
   
        int n = nums.size();
        int sum = 0, target = 0;
        for(int i = 0; i < n; i++)
            sum += nums[i];
        target = sum - x, sum = 0;
        int len = -1;

        if(target < 0) return -1;
        for(int left = 0, right = 0; right < n; right++)
        {
   
   
            sum += nums[right]; // 进窗口
            while(sum > target) // 判断
            {
   
   
                sum -= nums[left++]; // 出窗口
            }
            if(sum == target) // 更新结果
                len = max(len, right - left + 1);
        }

        return len == -1 ? len : n - len;
    }
};

image.png


5. leetcode904 水果成篮

image.png

水果成篮

这道题目的解法是利用滑动窗口+哈希表,数组中的元素表示水果种类的编号,我们只需要利用滑动窗口来进行解决,找到在篮子中的水果种类不超过2的情况下,求出窗口最长的情况即可。

代码实现:

class Solution {
   
   
public:
    int totalFruit(vector<int>& fruits) {
   
   
        int n = fruits.size(), hash[100010] = {
   
   0}, kinds = 0, len = 0;
        for(int left = 0, right = 0; right < n; right++)
        {
   
   
            if(++hash[fruits[right]] == 1) // 进窗口
                kinds++;
            while(kinds > 2) // 判断
            {
   
   
                if(--hash[fruits[left++]] == 0) // 出窗口
                    kinds--;
            }
            if(kinds <= 2) // 更新结果
                len = max(len, right - left + 1);
        }
        return len;
    }
};

image.png


6. leetcode438 找到字符串中所有字母异位词

image.png

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

这道题目依旧是利用滑动窗口+哈希表,我们可以先统计目标单词中出现的次数,将其映射到哈希表。维护一个判断窗口中有效字符的个数的变量cnt,从左向右依次利用滑动窗口遍历即可,这里因为单词的长度是固定的,因此每进一个窗口、如过窗口长度大于单词的长度,就必须让最左边的元素出窗口。

代码实现:

class Solution {
   
   
public:
    vector<int> findAnagrams(string s, string p) {
   
   
        vector<int> ret;
        int hash1[26] = {
   
   0}, hash2[26] = {
   
   0}, len = p.size();
        for(auto&e : p)
            hash2[e - 'a']++;
        int cnt = 0;//判断窗口中的有效字符
        for(int left = 0, right = 0; right < s.size(); right++)
        {
   
   
            if(++hash1[s[right] - 'a'] <= hash2[s[right] - 'a']) //进窗口
                cnt++;
            if(right - left + 1 > len) // 判断
            {
   
   
                if(--hash1[s[left] - 'a'] < hash2[s[left] - 'a']) //出窗口
                    cnt--;
                left++;
            }
            //判断结构是否合法
            if(cnt == len) // 更新结果
                ret.emplace_back(left);
        }
        return ret;
    }
};

image.png


7. leetcode30 串联所有单词的子串

image.png

串联所有单词的子串

这道题目和上一道题目很相似,无非就是上一道题目解决的是字符,这道题目解决的是字符串。依然使用的方法是滑动窗口+哈希表,因为这里提前告诉我了我们——目标字符串数组中的每个单词的长度都相同。所以根据这个条件我们可以大大降低时间复杂度。

image.png

这里我们需要注意的是,滑动窗口在出入窗口的过程中,移动的步长是单词的长度,滑动窗口执行的次数是单词的长度次。

代码实现:

class Solution {
   
   
public:
    vector<int> findSubstring(string s, vector<string>& words) {
   
   
        unordered_map<string,int> hash2;//开两个哈希表
        for(auto& e : words)
            hash2[e]++;
        vector<int> ret;
        ret.reserve(s.size());
        int len = words.size(), cnt = 0, n = words[0].size();
        for(int i = 0; i < n; i++) // 执行n次
        {
   
   
            unordered_map<string,int> hash1; // 维护窗口内单词的频次
            cnt = 0; 
            for(int left = i, right = i + n; right <= s.size(); right += n)
            {
   
   
                string tmp = s.substr(right - n, n);
                if(hash2.count(tmp) && ++hash1[tmp] <= hash2[tmp])
                    cnt++;
                if(right - left > n*len) // 出窗口,维护cnt
                {
   
   
                    string tmp = s.substr(left, n);
                    if(hash2.count(tmp) && --hash1[tmp] < hash2[tmp])
                        cnt--;
                    left += n;
                }
                if(cnt == len) // 更新结果
                    ret.emplace_back(left);
            }
        }
        return ret;
    }
};

image.png


8. leetcode76 最小覆盖子串

image.png

最小覆盖子串

这里给出我们的目标字符串t中的字符种类可能是重复出现的。和上面的题目”找到字符串中所有字母异位词“有所不同:这里我们进窗口时的判断条件应该是:当窗口中出现的字符个数等于目标串某个字符的个数时,变量cnt++,这样保证最后入窗口的字符个数等于目标字符串中指定字符个数时,也就是更新条件成立时,窗口中字符的种类 目标字符串窗口中的字符个数一定是 >= 目标字符串的字符的。保证了窗口中的字符串一定是能够完全覆盖目标字符串。最后在满足判断更新条件的循环中不断出窗口,直到出到不能在出为止。

代码实现:

class Solution {
   
   
public:
    string minWindow(string s, string t) {
   
   
        int hash1[128] = {
   
   0}, hash2[128] = {
   
   0}, kinds = 0;
        for(auto ch : t)
            if(hash2[ch]++ == 0) kinds++;
        int cnt = 0, Min = INT_MAX, begin = -1;
        for(int left = 0, right = 0; right < s.size(); right++)
        {
   
   
            if(++hash1[s[right]] == hash2[s[right]])
                cnt++;
            while(cnt == kinds)
            {
   
   
                if(right - left + 1 < Min)
                    Min = right - left + 1, begin = left;
                char out = s[left++];
                if(hash1[out]-- == hash2[out])
                    cnt--;
            }
        }
        if(begin == -1) return "";
        else return s.substr(begin, Min);
    }
};

image.png


三、总结

滑动窗口算法是在给定特定窗口大小的数组或字符串上执行要求的操作。 该技术可以将一部分问题中的嵌套循环转变为一个单循环,因此它可以减少时间复杂度。 简而言之,滑动窗口算法在一个特定大小的字符串或数组上进行操作,而不在整个字符串和数组上操作,这样就降低了问题的复杂度,从而也达到降低了循环的嵌套深度。


相关文章
|
4月前
|
负载均衡 算法 关系型数据库
大数据大厂之MySQL数据库课程设计:揭秘MySQL集群架构负载均衡核心算法:从理论到Java代码实战,让你的数据库性能飙升!
本文聚焦 MySQL 集群架构中的负载均衡算法,阐述其重要性。详细介绍轮询、加权轮询、最少连接、加权最少连接、随机、源地址哈希等常用算法,分析各自优缺点及适用场景。并提供 Java 语言代码实现示例,助力直观理解。文章结构清晰,语言通俗易懂,对理解和应用负载均衡算法具有实用价值和参考价值。
大数据大厂之MySQL数据库课程设计:揭秘MySQL集群架构负载均衡核心算法:从理论到Java代码实战,让你的数据库性能飙升!
|
29天前
|
机器学习/深度学习 算法 文件存储
神经架构搜索NAS详解:三种核心算法原理与Python实战代码
神经架构搜索(NAS)正被广泛应用于大模型及语言/视觉模型设计,如LangVision-LoRA-NAS、Jet-Nemotron等。本文回顾NAS核心技术,解析其自动化设计原理,探讨强化学习、进化算法与梯度方法的应用与差异,揭示NAS在大模型时代的潜力与挑战。
257 6
神经架构搜索NAS详解:三种核心算法原理与Python实战代码
|
11天前
|
机器学习/深度学习 资源调度 算法
遗传算法模型深度解析与实战应用
摘要 遗传算法(GA)作为一种受生物进化启发的优化算法,在复杂问题求解中展现出独特优势。本文系统介绍了GA的核心理论、实现细节和应用经验。算法通过模拟自然选择机制,利用选择、交叉、变异三大操作在解空间中进行全局搜索。与梯度下降等传统方法相比,GA不依赖目标函数的连续性或可微性,特别适合处理离散优化、多目标优化等复杂问题。文中详细阐述了染色体编码、适应度函数设计、遗传操作实现等关键技术,并提供了Python代码实现示例。实践表明,GA的成功应用关键在于平衡探索与开发,通过精心调参维持种群多样性同时确保收敛效率
55 7
|
11天前
|
机器学习/深度学习 边缘计算 人工智能
粒子群算法模型深度解析与实战应用
蒋星熠Jaxonic是一位深耕智能优化算法领域多年的技术探索者,专注于粒子群优化(PSO)算法的研究与应用。他深入剖析了PSO的数学模型、核心公式及实现方法,并通过大量实践验证了其在神经网络优化、工程设计等复杂问题上的卓越性能。本文全面展示了PSO的理论基础、改进策略与前沿发展方向,为读者提供了一份详尽的技术指南。
47 0
粒子群算法模型深度解析与实战应用
|
5月前
|
机器学习/深度学习 监控 算法
员工上网行为监控软件中基于滑动窗口的C#流量统计算法解析​
在数字化办公环境中,员工上网行为监控软件需要高效处理海量网络请求数据,同时实时识别异常行为(如高频访问非工作网站)。传统的时间序列统计方法因计算复杂度过高,难以满足低延迟需求。本文将介绍一种基于滑动窗口的C#统计算法,通过动态时间窗口管理,实现高效的行为模式分析与流量计数。
137 2
|
7月前
|
人工智能 编解码 算法
DeepSeek加持的通义灵码2.0 AI程序员实战案例:助力嵌入式开发中的算法生成革新
本文介绍了通义灵码2.0 AI程序员在嵌入式开发中的实战应用。通过安装VS Code插件并登录阿里云账号,用户可切换至DeepSeek V3模型,利用其强大的代码生成能力。实战案例中,AI程序员根据自然语言描述快速生成了C语言的base64编解码算法,包括源代码、头文件、测试代码和CMake编译脚本。即使在编译错误和需求迭代的情况下,AI程序员也能迅速分析问题并修复代码,最终成功实现功能。作者认为,通义灵码2.0显著提升了开发效率,打破了编程语言限制,是AI编程从辅助工具向工程级协同开发转变的重要标志,值得开发者广泛使用。
8510 71
DeepSeek加持的通义灵码2.0 AI程序员实战案例:助力嵌入式开发中的算法生成革新
|
3月前
|
存储 机器学习/深度学习 监控
公司电脑上网监控中滑动窗口算法的理论构建与工程实现
本文提出一种基于滑动窗口算法的实时网络流量监控框架,旨在强化企业信息安全防护体系。系统采用分层架构设计,包含数据采集、处理与分析决策三大模块,通过 Java 实现核心功能。利用滑动窗口技术动态分析流量模式,结合阈值检测与机器学习模型识别异常行为。实验表明,该方案在保证高检测准确率的同时支持大规模并发处理,为企业数字化转型提供可靠保障。
91 0
|
5月前
|
存储 机器学习/深度学习 监控
如何监控员工的电脑——基于滑动时间窗口的Java事件聚合算法实现探析​
在企业管理场景中,如何监控员工的电脑操作行为是一个涉及效率与合规性的重要课题。传统方法依赖日志采集或屏幕截图,但数据量庞大且实时性不足。本文提出一种基于滑动时间窗口的事件聚合算法,通过Java语言实现高效、低资源占用的监控逻辑,为如何监控员工的电脑提供一种轻量化解决方案。
130 3
|
6月前
|
存储 监控 算法
基于 PHP 语言的滑动窗口频率统计算法在公司局域网监控电脑日志分析中的应用研究
在当代企业网络架构中,公司局域网监控电脑系统需实时处理海量终端设备产生的连接日志。每台设备平均每分钟生成 3 至 5 条网络请求记录,这对监控系统的数据处理能力提出了极高要求。传统关系型数据库在应对这种高频写入场景时,性能往往难以令人满意。故而,引入特定的内存数据结构与优化算法成为必然选择。
144 3
|
9月前
|
算法

热门文章

最新文章