Java算法-滑动窗口算法(Sliding Window)（十），面试官最爱问的Kafka_滑动窗口算法java

2. 该技术可以将一部分问题中的嵌套循环转变为一个单循环，因此它可以减少时间复杂度。

基本示例

如下图所示，设定滑动窗口（window）大小为 3，当滑动窗口每次划过数组时，计算当前滑动窗口中元素的和，得到结果 res。

可以用来解决一些查找满足一定条件的连续区间的性质（长度等）的问题。由于区间连续，因此当区间发生变化时，可以通过旧有的计算结果对搜索空间进行剪枝，这样便减少了重复计算，降低了时间复杂度。往往类似于“ 请找到满足 xx 的最 x 的区间（子串、子数组）的 xx ”这类问题都可以使用该方法进行解决。

需要注意的是，滑动窗口算法更多的是一种思想，而非某种数据结构的使用。

在介绍滑动窗口的框架时候，大家先从字面理解下：

• 滑动：说明这个窗口是移动的，也就是移动是按照一定方向来的。

• 窗口：窗口大小并不是固定的，可以不断扩容直到满足一定的条件；也可以不断缩小，直到找到一个满足条件的最小窗口；当然也可以是固定大小。

算法实例

1. 题目描述

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口 k 内的数字。滑动窗口每次只向右移动一位。

返回滑动窗口最大值。

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3

输出: [3,3,5,5,6,7]

解题思路

代码实现

public static int [] maxSlidingWindow(int [] nums,int k) {

int[] res = new int[nums.length - k + 1];

LinkedList l = new LinkedList<>();

for (int i = 0; i < nums.length; i++) {

l.add(nums[i]);

// 循环当 集合长度等于 k 吧0 位置数据 添加至res

if (l.size() == k) {

res[i - k+1] = Collections.max(l);

l.removeFirst();

}

}

return res;

}

2. 题目描述

给定一个字符串如：“accekcbbt”，请你找出其中不含有重复字符的 最长子串 的长度。

建立一个集合存放 每个字符;

a

a c 找到集合长度为2的连续不同数据，寻找以3为窗口是否存在连续不同数据，

a c c 3为窗口,添加新数据，存在重复删除 0位置数据

c c e 3为窗口,添加新数据，存在重复删除 0位置数据

c e k 找到集合长度为3的连续不同数据， 寻找以4为窗口是否存在连续不同数据

c e k c 4为窗口,添加新数据，存在重复删除 0位置数据

e k c b 找到集合长度为3的连续不同数据， 寻找以4为窗口是否存在连续不同数据

e k c b b 5为窗口,添加新数据，存在重复删除 0位置数据

k c b b t 5为窗口,添加新数据，存在重复删除 0位置数据

结果 5为窗口的连续不同数据 没有找到，现在数组中存放的数据长度为最大移动窗口

代码实现

public static int maxStrSlidingWindow(String str){

LinkedList l = new LinkedList<>();

for (int i = 0; i < str.length(); i++) {

char c = str.charAt(i);

l.add©;

long count = l.stream().distinct().count();

if(l.size() != count){

l.removeFirst();

}

}

return l.size();

}

3. 题目描述

给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的绝对值最大为 k。

• 示例 1:

输入: nums = [1,2,3,1], k = 3

输出: true

• 示例 2:

输入: nums = [1,0,1,1], k = 1

输出: true

• 示例 3:

输入: nums = [1,2,3,1,2,3], k = 2

输出: false

代码实现

public static boolean containsStrSlidingWindow(int[] nums, int k){

LinkedList integers = new LinkedList<>();

for (int i = 0; i < nums.length; i++) {

if(integers.contains(nums[i])){

return true;

}

integers.add(nums[i]);

if(integers.size()>k){

integers.removeFirst();

}

}

return false;

}

4. 题目描述

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0；

输入: s = 7, nums = [2,3,1,2,4,3]

输出: 2

解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。

小编13年上海交大毕业，曾经在小公司待过，也去过华为、OPPO等大厂，18年进入阿里一直到现在。

深知大多数初中级Java工程师，想要提升技能，往往是自己摸索成长，但自己不成体系的自学效果低效又漫长，而且极易碰到天花板技术停滞不前！

因此收集整理了一份《2024年最新Java开发全套学习资料》送给大家，初衷也很简单，就是希望能够帮助到想自学提升又不知道该从何学起的朋友，同时减轻大家的负担。

由于文件比较大，这里只是将部分目录截图出来，每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频

如果你觉得这些内容对你有帮助，可以添加下面V无偿领取！（备注Java）

最后

现在其实从大厂招聘需求可见，在招聘要求上有高并发经验优先，包括很多朋友之前都是做传统行业或者外包项目，一直在小公司，技术搞的比较简单，没有怎么搞过分布式系统，但是现在互联网公司一般都是做分布式系统。

所以说，如果你想进大厂，想脱离传统行业，这些技术知识都是你必备的，下面自己手打了一份Java并发体系思维导图，希望对你有所帮助。

[外链图片转存中…(img-bx1eW3Qf-1711142494469)]

最后

现在其实从大厂招聘需求可见，在招聘要求上有高并发经验优先，包括很多朋友之前都是做传统行业或者外包项目，一直在小公司，技术搞的比较简单，没有怎么搞过分布式系统，但是现在互联网公司一般都是做分布式系统。

所以说，如果你想进大厂，想脱离传统行业，这些技术知识都是你必备的，下面自己手打了一份Java并发体系思维导图，希望对你有所帮助。

[外链图片转存中…(img-xKUvKT4b-1711142494469)]

本文已被CODING开源项目：【一线大厂Java面试题解析+核心总结学习笔记+最新讲解视频+实战项目源码】收录