详解顺序结构滑动窗口处理算法

🎀个人主页: https://zhangxiaoshu.blog.csdn.net
📢欢迎大家:关注🔍+点赞👍+评论📝+收藏⭐️,如有错误敬请指正!
💕未来很长,值得我们全力奔赴更美好的生活!

前言

在数据结构和算法方面的面试中,数组和字符串的相关问题往往是一个重要的考察点。面试官通常会测试面试者在处理这些基础数据结构时的熟练程度,因为这直接关系到解决实际问题的能力。在数组和字符串的考察中,双指针和滑动窗口以及排序算法、字符串的处理API成为关键技巧,本文主要对滑动窗口进行简单介绍。


文章目录

  • 前言
  • 1. 序
  • 2. 滑动窗口原理
  • 3. 应用场景
    • (1)长度最小的子数组
    • (2)无重复字符的最长子串
    • (3)存在重复元素 II
  • 总结


1. 序

双指针和滑动窗口是在处理数组和字符串问题时常用的技巧。双指针通常用于解决数组中的一些查找或判断问题,通过设置两个指针在数组上移动,实现对数组的遍历和比较。滑动窗口则常用于解决字符串中的子串或子数组问题,通过维护一个可变大小的窗口在字符串上滑动,从而实现对子串或子数组的探测。

排序算法在面试中同样是一个重要的考察点,因为它与数组相关,对数据的整理和查找提供了基础。熟练掌握常见的排序算法,如快速排序、归并排序等,有助于在解决各种问题时更高效地处理数组。此外,对于字符串的处理API也是面试中需要掌握的知识。熟悉字符串的各种操作,如查找子串、替换字符、反转字符串等,能够帮助面试者更灵活地处理字符串相关的问题。

本文主要是对滑动窗口这种常用技巧进行简要介绍,帮助读者在面对数组和字符串相关问题时能够更加从容应对。深入理解这些技巧,并在实际问题中灵活运用,将有助于提高面试者在数据结构和算法面试中的表现。

2. 滑动窗口原理

滑动窗口法是一种在处理数组或字符串的子序列(子数组或子串)问题时常用的技巧。它通过维护一个动态的窗口来解决问题,窗口的起始和结束位置会根据问题的要求进行滑动。这种方法通常用于求解最长子串、最短子数组等问题。

在这里插入图片描述

基本思路:

  1. 初始化窗口的起始位置和结束位置。通常使用两个指针,比如 start 和 end,表示窗口的左右边界。

  2. 通过移动窗口的结束位置,扩大窗口。根据问题的要求,可以通过增加 end 指针的位置来扩展窗口。

  3. 通过移动窗口的起始位置,缩小窗口。当窗口包含的元素满足某个条件时,可以通过增加 start 指针的位置来缩小窗口。

  4. 重复以上步骤直到满足问题的条件。 在每一步中,都可以根据问题的要求更新窗口的状态,并在遍历完整个数组或字符串后得到问题的解。

滑动窗口法的优势在于它能够在线性时间内解决很多子序列问题,而无需使用额外的空间。这使得它在处理大规模数据时表现良好。

3. 应用场景

(1)长度最小的子数组

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

具体思路如下:

  • 初始化变量 ans 为整数的最大值 Integer.MAX_VALUE,start 和 end 分别表示当前子数组的起始和结束位置,sum 表示当前子数组的和。

  • 使用 while 循环遍历数组 nums,其中 end 指针负责扩大窗口,start 指针负责缩小窗口。

  • 在循环中,先将当前元素加到 sum 中,然后检查是否满足 sum >= target 的条件。如果满足,说明当前窗口的子数组和大于等于目标值,此时进入内部的 while 循环。

  • 在内部的 while 循环中,不断缩小窗口,即通过减去 nums[start] 的值来减小 sum。同时,更新 ans 为当前窗口的长度 end - start + 1 和 ans 之前值的较小值。这样,通过不断缩小窗口,可以找到满足条件的最小子数组。

  • 重复上述过程,直到 end 指针遍历完整个数组。

  • 返回最终结果 ans,如果 ans 仍然为 Integer.MAX_VALUE,说明没有找到满足条件的子数组,返回 0;否则,返回找到的最小子数组的长度。

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

(2)无重复字符的最长子串

给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。

具体思路如下:

  • 初始化指针和数据结构: 使用 start 和 end 两个指针来表示当前子串的起始和结束位置,使用 HashSet 来存储当前子串中出现的字符。lenMax 用于记录最长不含重复字符的子串长度。

  • 滑动窗口: 通过不断移动 end 指针,扩大窗口。当遇到重复字符时,开始缩小窗口。

  • 处理重复字符:如果当前字符是新字符,将其添加到 set 中,然后更新 lenMax 为当前子串的长度(end - start + 1)的最大值。如果当前字符已经在 set 中,表示有重复字符,需要将 start 指针右移,并将对应的字符从 set 中移除,直到子串中不再包含重复字符。

  • 遍历完整个字符串: 通过不断移动 end 指针和更新 lenMax,直到 end 指针遍历完整个字符串。

  • 返回结果: 返回最终的 lenMax,即最长不含重复字符的子串的长度。

class Solution {public int lengthOfLongestSubstring(String s) {int start=0;int end=0;HashSet<Character> set = new HashSet<Character>();int lenMax=0;while(end < s.length()){          if(set.add(s.charAt(end))){lenMax=Math.max(lenMax,end-start+1);end++;      }else{set.remove(s.charAt(start));start++;}}return lenMax;}
}

(3)存在重复元素 II

给你一个整数数组 nums 和一个整数 k ,判断数组中是否存在两个 不同的索引 i 和 j ,满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在,返回 true ;否则,返回 false 。
输入:nums = [1,2,3,1], k = 3
输出:true

  • 初始化数据结构: 使用一个 LinkedHashSet 来存储当前窗口中的元素,保持插入顺序。

  • 遍历数组: 使用两个指针 start 和 end 遍历数组,其中 end 指针负责扩大窗口,start 指针负责缩小窗口。

  • 判断重复元素: 在每一步中,首先检查当前窗口中是否包含数组中的元素 nums[end]。如果存在,表示存在重复元素,直接返回 true。

  • 保持窗口大小: 在窗口大小达到 k 之后,通过缩小窗口,即移除 set 中的元素 nums[start],并将 start 指针右移。

  • 遍历完整个数组: 重复上述步骤,直到 end 指针遍历完整个数组。

  • 返回结果: 如果在遍历过程中未找到重复元素,返回 false。

class Solution {public boolean containsNearbyDuplicate(int[] nums, int k) {int numLength = nums.length;Set<Integer> set = new LinkedHashSet<>();for(int start = 0, end = 0; end < numLength; end++){if(set.contains(nums[end])){return true;}set.add(nums[end]);while (end - start >= k){set.remove(nums[start]);start++;}}return false;}
}

总结

滑动窗口算法是一种用于解决数组或字符串中子序列(子数组或子串)问题的有效技巧。它通过维护一个动态的窗口,不断调整窗口的起始和结束位置,以满足问题的条件。以下是滑动窗口算法的关键特点、优势和应用场景:

  1. 关键特点:
  • 使用两个指针(通常是起始指针和结束指针)表示窗口的边界。
  • 通过不断移动窗口的边界,动态调整窗口的大小。
  • 用于解决需要求解子序列最优解的问题。
  1. 优势:
  • 高效: 滑动窗口算法通常具有线性时间复杂度,因为每个元素或字符只需被访问一次。
  • 空间效率: 使用常数级的额外空间,不需要存储整个子序列的信息,而是通过维护窗口的边界来解决问题。
  • 简洁: 算法思路相对简单,易于理解和实现。
  1. 应用场景:
  • 最长子串或子数组: 用于求解最长不含重复字符的子串、最短子数组等问题。
  • 满足条件的子串: 用于找到满足特定条件的子串,如包含指定字符、和大于等于某个值的子数组等。
  • 窗口内的统计信息: 用于在移动窗口的过程中动态计算窗口内元素的统计信息,如和、平均值等。
  • 固定长度的窗口: 用于处理固定长度的窗口,例如计算滑动窗口的平均值。
  1. 注意事项:
  • 确保窗口的起始和结束位置的移动是合理的,避免重复计算和漏算。
  • 处理窗口的边界条件,确保不越界。

总体来说,滑动窗口算法是一种高效、简洁的解决子序列问题的方法,在处理字符串和数组等数据结构时广泛应用。

文中有不对的地方欢迎指正、补充。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/2812478.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

python Matplotlib Tkinter-->tab切换2

环境 python:python-3.12.0-amd64 包: matplotlib 3.8.2 pillow 10.1.0 import matplotlib.pyplot as plt from matplotlib.backends.backend_tkagg import FigureCanvasTkAgg, NavigationToolbar2Tk import tkinter as tk import tkinter.ttk as ttk# 创建自定义工具栏类 c…

nginx---------------重写功能 防盗链 代理 (五)

一、重写功能 rewrite Nginx服务器利用 ngx_http_rewrite_module 模块解析和处理rewrite请求&#xff0c;此功能依靠 PCRE(perl compatible regular expression)&#xff0c;因此编译之前要安装PCRE库&#xff0c;rewrite是nginx服务器的重要功能之一&#xff0c;重写功能(…

各类几何像差

1、离焦&#xff1a; 简单理解&#xff0c;离焦就是成像面不在焦点处&#xff1a; 越远&#xff0c;越模糊 2、球差&#xff1a; 球差是由于透镜中心区域和边缘区域对电磁波会聚能力不同而造成的。远轴电磁波通过透射时被折射得比近轴电磁波要厉害得多&#xff0c;因而由同一…

vue3使用elementPlus进行table合并处理

elementPlus中table合并部分列 虚拟数据中公司下有多个客户&#xff0c;公司一样的客户&#xff0c;公司列需要合并&#xff0c;客户如果一样也需要合并进行展示&#xff0c;效果展示 const tableData ref([])自定定义自已想要的数据&#xff0c;一般都是通过接口拿到 //table…

后端:跨端轻量JavaScript引擎的实现与探索

一、JavaScript 1.JavaScript语言 JavaScript是ECMAScript的实现,由ECMA 39(欧洲计算机制造商协会39号技术委员会)负责制定ECMAScript标准。 ECMAScript发展史: 时间版本说明1997年7月ES1.0 发布当年7月&#xff0c;ECMA262 标准出台1998年6月ES2.0 发布该版本修改完全符合…

Netty权威指南——基础篇2(NIO编程)

1 概述 与Socket类和ServerSocket&#xff0c;NIO也提供了SocketChannel和ServerSocketChannel两种不同的套接字通道实现。这两种新增的通道都支持阻塞和非阻塞两种模式。阻塞模式使用简单&#xff0c;但性能和可靠性都不好&#xff0c;非阻塞模式则正好相反。一般来说&#xf…

康复训练day2——2024牛客寒假集训营6

一道很好的构造题&#xff0c;受益匪浅。 链接&#xff1a;F-命运的抉择_2024牛客寒假算法基础集训营6 (nowcoder.com)​​​​​​ 题意&#xff1a; 题解 &#xff08;并查集 思维&#xff09;&#xff1a; 首先将存在1的情况特判掉&#xff0c;我们的数组的元素都是> 2的…

告别 Axure 卡顿!国产原型设计工具,体验更流畅

原型设计工具的应用场景包括产品展示、产品需求规划和抽象到具体呈现&#xff0c;那么如何根据应用场景选择合适的原型工具呢&#xff1f;不用说&#xff0c;本文列出了常用的原型设计工具&#xff0c;看看你最想选择哪一个&#xff01; 即时设计 即时设计具有一站式原型、设…

【lv14 day10内核模块参数传递和依赖】

一、模块传参 module_param(name,type,perm);//将指定的全局变量设置成模块参数 /* name:全局变量名 type&#xff1a; 使用符号 实际类型 传参方式 bool bool insmod xxx.ko 变量名0 或 1 invbool bool insmod xxx.ko 变量名0 或 1 charp char * insmod xxx.ko 变量名“字符串…

Facebook与社交创新:数字时代的社交构建者

在当今数字化时代&#xff0c;社交媒体已经成为人们日常生活中不可或缺的一部分。而在这个庞大的社交网络中&#xff0c;Facebook作为其中的巨头之一&#xff0c;不仅扮演着连接人们的桥梁&#xff0c;更是社交创新的领导者和推动者。本文将探讨Facebook在数字时代的社交构建中…

python Matplotlib Tkinter-->最终框架一

3D雷达上位机实例(能够通过点击柱状图来展示3D雷达数据)2024.2.26 环境 python:python-3.12.0-amd64 包: matplotlib 3.8.2 pillow 10.1.0 import matplotlib.pyplot as plt from matplotlib.backends.backend_tkagg import FigureCanvasTkAgg, NavigationToolbar2Tk impor…

react useMemo 用法

1&#xff0c;useCallback 的功能完全可以由 useMemo 所取代&#xff0c;如果你想通过使用 useMemo 返回一个记忆函数也是完全可以的。 usecallback(fn,inputs)is equivalent to useMemo(()> fn, inputs). 区别是:useCallback不会执行第一个参数函数&#xff0c;而是将它返…

领先科技2024年3月5-7日第12届国际生物发酵展-宁泰橡塑

参展企业介绍 湖南宁泰橡塑有限公司&#xff08;简称“宁泰”&#xff09;位于国家 级湖南省浏阳经济技术开发区&#xff0c;距离省会城市长沙35公里&#xff0c;距离黄花国际机场18公里&#xff0c;交通便利&#xff0c;区位和地缘优势明显。宁泰是一家专业从事卫生级橡塑制品…

cmake 构建Qt存在多个子项目的应用

概述&#xff1a;一般在开发UI应用时候我们都会存在多个子项目&#xff0c;比如一个是主UI界面的项目&#xff0c;有些动态库的项目&#xff0c;主UI中用到子项目中的动态库&#xff0c;我们来看看如何利用cmake来构建这样的一个工程&#xff0c;方便我们在跨平台中开发(macos、…

安防视频监控平台EasyNVR级联视频上云管理平台EasyNVS,出现报错“i/o deadline reached”该如何解决?

上云网关管理平台EasyNVS视频综合管理系统具备汇聚与管理EasyGBS、EasyNVR等平台的能力&#xff0c;系统可以将接入的视频资源实现视频能力统一输出&#xff0c;并能进行远程可视化运维等管理功能&#xff0c;还能解决设备现场没有固定公网IP却需要在公网直播的需求。 有用户反…

golang gin单独部署vue3.0前后端分离应用

概述 因为公司最近的项目前端使用vue 3.0&#xff0c;后端api使用golang gin框架。测试通过后&#xff0c;博文记录&#xff0c;用于备忘。 步骤 npm run build&#xff0c;构建出前端项目的dist目录&#xff0c;dist目录的结构具体如下图 将dist目录复制到后端程序同级目录…

Bluesky数据采集框架-4

编写自定义计划 如在以上简单自定义中提到&#xff0c;count()和scan()的"预装配"计划是从更小的"plan stubs"构建的。我们组合和匹配"stubs"和/或"预装配"计划来构建自定义计划。 有很多计划stubs&#xff0c;因此导入整个模块并且…

低价对品牌渠道的危害

品牌价值的体现主要在价格&#xff0c;比如要与竞品体现差异&#xff0c;除了产品功能上有做出差异&#xff0c;价格上也需要设置不同的阶梯&#xff0c;但如果经销商不遵守这个体系&#xff0c;或者非授权店铺随意低价&#xff0c;对于品牌来说都是非常不好的事情&#xff0c;…

ubuntu20.04安装和使用 Maldet (Linux Malware Detect)

1、下载 Maldet sudo wget http://www.rfxn.com/downloads/maldetect-current.tar.gz 2、解压Maldet sudo tar -xvf maldetect-current.tar.gz 3、进入到Maldet目录&#xff0c;然后运行安装脚本 sudo ./install.sh 4、安装ClamAV sudo apt-get update sudo apt-get in…

【程序员英语】【美语从头学】初级篇(入门)(笔记)Lesson 16 At the Shoe Store 在鞋店

《美语从头学初级入门篇》 注意&#xff1a;被 删除线 划掉的不一定不正确&#xff0c;只是不是标准答案。 文章目录 Lesson 16 At the Shoe Store 在鞋店对话A对话B笔记会话A会话B替换 Lesson 16 At the Shoe Store 在鞋店 对话A A: Do you have these shoes in size 8? B:…