网站项目建设策划书流程,南昌市，做网站的公司,平谷手机网站设计,网络营销包括文章目录 前言什么是滑动窗口1.长度最小的子数组1.1 题目要求1.2 做题思路 1.3 Java代码实现2.无重复字符的最长子串2.1 题目要求2.2 做题思路2.3 Java代码实现 3.最大连续1的个数 III3.1 题目要求3.2 做题思路3.3 Java代码实现 4.将x减到0的最小操作数4.1 题目要求4.2 做题思路… 文章目录 前言什么是滑动窗口1.长度最小的子数组1.1 题目要求1.2 做题思路 1.3 Java代码实现2.无重复字符的最长子串2.1 题目要求2.2 做题思路2.3 Java代码实现 3.最大连续1的个数 III3.1 题目要求3.2 做题思路3.3 Java代码实现 4.将x减到0的最小操作数4.1 题目要求4.2 做题思路4.3 Java代码实现 5.水果成篮5.1 题目要求5.2 做题思路5.3 Java代码实现 6.找到字符串中所有字母异位词6.1 题目要求6.2 做题思路6.3 Java代码实现 7.串联所有单词的子串7.1 题目要求7.2 做题思路7.3 Java代码实现 8.最小覆盖字串8.1 题目要求8.2 做题思路8.3 Java代码实现 总结 前言
前面我们学习了什么是双指针今天我将为大家分享一种特殊的双指针——滑动窗口为什么说它是特殊的双指针呢因为它也是有两个指针维护的并且两个指针的移动方向是相同的就跟我们平时生活中的窗口一样两条边是往相同的方向移动的。
什么是滑动窗口
滑动窗口算法是一种用于解决数组或字符串相关问题的算法。它通过两个指针维护的一个窗口在窗口内进行操作并根据问题的要求移动窗口的起始位置或结束位置。
滑动窗口算法通常用于解决需要在连续子数组或子字符串中寻找最大值、最小值、满足特定条件的值等问题。它的基本思想是通过调整窗口的大小和位置以便在不重复计算的情况下高效地处理问题。
滑动窗口算法的步骤如下
初始化窗口的起始位置和结束位置。根据问题的要求移动窗口的起始位置或结束位置。在每次移动窗口时根据窗口内的元素进行相应的操作例如计算最大值、最小值、满足特定条件的值等。重复步骤2和步骤3直到窗口移动到数组或字符串的末尾。
滑动窗口算法的时间复杂度通常为O(n)其中n为数组或字符串的长度。它通过避免重复计算提高了问题的解决效率。
我们通过几个例子来了解滑动窗口算法。
1.长度最小的子数组
https://leetcode.cn/problems/minimum-size-subarray-sum/
1.1 题目要求
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl1, …, 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提示
1 target 109
1 nums.length 105
1 nums[i] 105class Solution {public int minSubArrayLen(int target, int[] nums) {}
}1.2 做题思路
我们先来看看如果使用暴力解法该怎么做。分别以每个数字开始向后找 和target的子数组。 暴力解法是通过两层循环i 从 0开始j 从 i1 开始遍历整个数字找到 和 target 的长度最小的子数组。并且这个和是每次循环都从 0 开始加的。
通过观察每次循环找到的长度最小的子数组我们可以发现left 指针和 right 指针都是向同一个方向向右移动的暴力解法是每次循环结束之后 right 的位置就回到 left 1 的位置这样就多了很多重复的不必要的计算。所以滑动窗口就是在这个暴力解法的基础上进行优化的每次 right 的指向不进行返回而是继续向右滑动那么为什么 right 的指向可以不用返回呢因为每次循环 left 的指向都会向右移动一位而你要想找的长度最小的子数组的和 target你的 right 就必须也是向右移动或者不移动但是绝对不会是向左移动在数组元素都是正数的情况下这种就是滑动窗口的基本特征。
那么知道了使用滑动窗口这个算法的时候我们来看看具体应该如何实现。定义一个 sum 变量存储每次进窗口之后这个窗口元素的和并且这个sum 不是每一次都是逐个累加而是用之前的 sum 加上进窗口的这个元素当 sum target 的时候就需要进行出窗口的操作并且在出窗口的时候还需要判断是否需要更新 ret 的值继续寻找后面的长度最小的子数组每出一个元素sum 就需要减去这个出去的数出窗口一直出到 sum target然后再进窗口反复上面的操作直到 right 到达数组末尾。 1.3 Java代码实现
class Solution {public int minSubArrayLen(int target, int[] nums) {int ret Integer.MAX_VALUE;for(int left 0,right 0, sum 0; right nums.length; right) {sum nums[right];while(sum target) {ret Math.min(ret,right - left 1);sum - nums[left];}}return ret Integer.MAX_VALUE ? 0 : ret;}
}2.无重复字符的最长子串
https://leetcode.cn/problems/longest-substring-without-repeating-characters/
2.1 题目要求
给定一个字符串 s 请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s abcabcbb
输出: 3
解释: 因为无重复字符的最长子串是 abc所以其长度为 3。示例 2:
输入: s bbbbb
输出: 1
解释: 因为无重复字符的最长子串是 b所以其长度为 1。示例 3:
输入: s pwwkew
输出: 3
解释: 因为无重复字符的最长子串是 wke所以其长度为 3。请注意你的答案必须是 子串 的长度pwke 是一个子序列不是子串。提示
0 s.length 5 * 104
s 由英文字母、数字、符号和空格组成class Solution {public int lengthOfLongestSubstring(String s) {}
}2.2 做题思路
先来看看暴力解法如何解决 通过暴力解法我们也可以发现每次循环找到的无重复字符的最长子串它的 left 的 right 都是向右移动的所以这个题目同样使用滑动窗口来解决。
因为这里求的是长度最长的无重复字符的子串所以需要在进窗口的时候进行判断是否需要更新最大长度而判断是否有重复的字符我们可以借助哈希表来进行判断。 2.3 Java代码实现
class Solution {public int lengthOfLongestSubstring(String ss) {char[] s ss.toCharArray();int[] hash new int[128];int ret 0;for(int left 0, right 0; right s.length; right) {char in s[right];hash[in];if(hash[in] 1) {ret Math.max(ret,right - left 1);}while(hash[in] 1) {char out s[left];hash[out]--;}}return ret;}
}3.最大连续1的个数 III
https://leetcode.cn/problems/max-consecutive-ones-iii/
3.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。提示
1 nums.length 105
nums[i] 不是 0 就是 1
0 k nums.lengthclass Solution {public int longestOnes(int[] nums, int k) {}
}3.2 做题思路
很多人看到这个翻转0不知道啥意思说通俗点就是0可以变成1同样先来看看暴力解法如何解决。 left 指针和 right 指针都是向右方向移动的所以这道题目同样使用滑动窗口来解决。我们的判断条件是以窗口内0的数量为判断条件并且求的是最大长度所以是在进窗口的时候进行判断。 3.3 Java代码实现
class Solution {public int longestOnes(int[] nums, int k) {int ret 0;for(int left 0, right 0,count 0; right nums.length; right) {if(nums[right] 0) count;if(count k) {ret Math.max(ret,right - left 1);}while(count k) {if(nums[left] 0) count--;}}return ret;}
}4.将x减到0的最小操作数
https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/
4.1 题目要求
给你一个整数数组 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 。提示
1 nums.length 105
1 nums[i] 104
1 x 109class Solution {public int minOperations(int[] nums, int x) {}
}4.2 做题思路
这道题目的意思就是给定一个数字x每次从数组的最左边或者最右边选择一个数减去然后使x减到0的最少的操作数。这道题目如果从正面去做的话会先的非常麻烦不妨我们换一条思路他求的是数组两边减去的最少的数字不妨我们就求数组中间最长的子数组使它们的和为数组所有元素的总和减去 target 这样就能是数组的两侧的和为 target 并且长度最短。所以这个题目就跟前面的求数组长度最长的子数组是差不多的就只是判断的地方不同这里需要在出窗口之后判断是否需要更新ret的值这里我就不给大家过多介绍了关键就是能够知道这个思路。
4.3 Java代码实现
class Solution {public int minOperations(int[] nums, int x) {int sum 0;for(int n : nums) sum n; //求数组所有元素的总和int target sum - x;if(target 0) return -1;int ret -1;for(int left 0, right 0,sum1 0; right nums.length; right) {sum1 nums[right];while(sum1 target) {sum1 - nums[left];}if(sum1 target) {ret Math.max(ret,right - left 1);}}return ret -1 ? -1 : nums.length - ret;}
}5.水果成篮
https://leetcode.cn/problems/fruit-into-baskets/
5.1 题目要求
你正在探访一家农场农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示其中 fruits[i] 是第 i 棵树上的水果 种类 。
你想要尽可能多地收集水果。然而农场的主人设定了一些严格的规矩你必须按照要求采摘水果
你只有 两个 篮子并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。你可以选择任意一棵树开始采摘你必须从 每棵 树包括开始采摘的树上 恰好摘一个水果 。采摘的水果应当* 符合篮子中的水果类型。每采摘一次你将会向右移动到下一棵树并继续采摘。一旦你走到某棵树前但水果不符合篮子的水果类型那么就必须停止采摘。
给你一个整数数组 fruits 返回你可以收集的水果的 最大 数目。
示例 1
输入fruits [1,2,1]
输出3
解释可以采摘全部 3 棵树。示例 2
输入fruits [0,1,2,2]
输出3
解释可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘则只能采摘 [0,1] 这两棵树。示例 3
输入fruits [1,2,3,2,2]
输出4
解释可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘则只能采摘 [1,2] 这两棵树。示例 4
输入fruits [3,3,3,1,2,1,1,2,3,3,4]
输出5
解释可以采摘 [1,2,1,1,2] 这五棵树。提示
1 fruits.length 105
0 fruits[i] fruits.lengthclass Solution {public int totalFruit(int[] fruits) {}
}5.2 做题思路
根据题目我们可以知道只有两个篮子只能装两种水果并且每个篮子可以装的水果数是无限的这道题跟子数组的问题是类似的只是判断条件变成了水果的种类进窗口的时候添加水果的种类很简单当这个种类的水果数量在之前为0时就说明是一个新的种类但是当我们出窗口的时候如果某一种类的水果数量减为0的时候就需要减去一种种类那么我们如何统计某一水果的数量呢哈希表使用哈希表可以很高效的对某一种类的数量进行统计。
5.3 Java代码实现
class Solution {public int totalFruit(int[] fruits) {int ret 1;int[] hash new int[fruits.length];for(int left 0, right 0,kinds 0; right fruits.length; right) {int in fruits[right];if(hash[in] 0) kinds;if(kinds 2) { //当水果的种类小于等于2的时候就需要做出判断ret Math.max(ret,right - left 1);}while(kinds 2) {int out fruits[left];if(--hash[out] 0) kinds--;}}return ret;}
}6.找到字符串中所有字母异位词
https://leetcode.cn/problems/find-all-anagrams-in-a-string/
6.1 题目要求
给定两个字符串 s 和 p找到 s 中所有 p 的 异位词 的子串返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串包括相同的字符串。
示例 1:
输入: s cbaebabacd, p abc
输出: [0,6]
解释:
起始索引等于 0 的子串是 cba, 它是 abc 的异位词。
起始索引等于 6 的子串是 bac, 它是 abc 的异位词。示例 2:
输入: s abab, p ab
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 ab, 它是 ab 的异位词。
起始索引等于 1 的子串是 ba, 它是 ab 的异位词。
起始索引等于 2 的子串是 ab, 它是 ab 的异位词。提示:
1 s.length, p.length 3 * 104
s 和 p 仅包含小写字母class Solution {public ListInteger findAnagrams(String s, String p) {}
}6.2 做题思路
这道题其实就相当于使用一个大小为 p 字符串长度的框从 s 字符串头部开始框 p 字符串长度的字符串然后判断框起来的字符串是否是 p 字符串的异位词。
窗口中的大小是确定的最终的窗口的大小是p字符串的长度也就是说我们的判断条件就是窗口内的字符串是否是p字符串的异位词这也是解决这道题的关键。那么我们应该如何解决呢同样是使用两个哈希表第一个哈希表统计p字符串每个单词出现的次数当进窗口的时候第二个哈希表中该字符出现的次数就加一并且如果将这个字符添加进哈希表之后该哈希表中对应字符出现的次数小于等于第一个哈希表对应字符出现的次数就说明进窗口的这个字符为有效字符我们使用 count 来记录有效字符的个数count当 count 等于 p 字符串的长度时就需要更新结果将 left 的坐标添加进列表中。
6.3 Java代码实现
class Solution {public ListInteger findAnagrams(String ss, String pp) {ListInteger list new ArrayList();char[] s ss.toCharArray();char[] p pp.toCharArray();int[] hash1 new int[26];int[] hash2 new int[26];for(char ch : p) hash1[ch - a];int len p.length;for(int left 0, right 0,count 0; right s.length; right) {char in s[right];if(hash2[in - a] hash1[in - a]) count;if(right - left 1 len) {char out s[left];if(hash2[out - a]-- hash1[out - a]) count--;}if(count len) {list.add(left);}}return list;}
}7.串联所有单词的子串
https://leetcode.cn/problems/substring-with-concatenation-of-all-words/
7.1 题目要求
给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。
s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。
例如如果 words [“ab”,“cd”,“ef”] 那么 “abcdef” “abefcd”“cdabef” “cdefab”“efabcd” 和 “efcdab” 都是串联子串。 “acdbef” 不是串联子串因为他不是任何 words 排列的连接。 返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。
示例 1
输入s barfoothefoobarman, words [foo,bar]
输出[0,9]
解释因为 words.length 2 同时 words[i].length 3连接的子字符串的长度必须为 6。
子串 barfoo 开始位置是 0。它是 words 中以 [bar,foo] 顺序排列的连接。
子串 foobar 开始位置是 9。它是 words 中以 [foo,bar] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。示例 2
输入s wordgoodgoodgoodbestword, words [word,good,best,word]
输出[]
解释因为 words.length 4 并且 words[i].length 4所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。示例 3
输入s barfoofoobarthefoobarman, words [bar,foo,the]
输出[6,9,12]
解释因为 words.length 3 并且 words[i].length 3所以串联子串的长度必须为 9。
子串 foobarthe 开始位置是 6。它是 words 中以 [foo,bar,the] 顺序排列的连接。
子串 barthefoo 开始位置是 9。它是 words 中以 [bar,the,foo] 顺序排列的连接。
子串 thefoobar 开始位置是 12。它是 words 中以 [the,foo,bar] 顺序排列的连接。提示
1 s.length 104
1 words.length 5000
1 words[i].length 30
words[i] 和 s 由小写英文字母组成class Solution {public ListInteger findSubstring(String s, String[] words) {}
}7.2 做题思路
这道题目跟上面的一个题目是类似的只是这里将字母换成了单词所以我们可以仿照上面一个题的思路将words数组中的每个字符串当作一个字母s 字符串每与words数组中每个单词相同长度的字符串作为一个字母。 因为不仅可以从 b 开始将字符数组分为多个字符串还可以从a和r开始所以这里我们需要进行 words 数组中每个单词长度的循环次数的操作。
这里的哈希表用数组就不容易模拟了所以这里就需要用到 HashMap
7.3 Java代码实现
class Solution {public ListInteger findSubstring(String s, String[] words) {ListInteger list new ArrayList();MapString,Integer map1 new HashMap();for(String tmp : words) {map1.put(tmp,map1.getOrDefault(tmp,0) 1);}int len words.length; //求words数组的大小int m words[0].length(); //求words数组中每个单词的长度for(int i 0; i m; i) {MapString,Integer map2 new HashMap();for(int left i, right i, count 0; right s.length()-m; right m) {String in s.substring(right,right m);map2.put(in,map2.getOrDefault(in,0) 1);if(map2.get(in) map1.getOrDefault(in,0)) count;if(right - left 1 len * m) {String out s.substring(left,left m);if(map2.get(out) map1.getOrDefault(out,0)) count--;map2.put(out,map2.get(out) - 1);left m;}if(count len) list.add(left);}}return list;}
}8.最小覆盖字串
https://leetcode.cn/problems/minimum-window-substring/
8.1 题目要求
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串则返回空字符串 “” 。
注意
对于 t 中重复字符我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串我们保证它是唯一的答案。示例 1
输入s ADOBECODEBANC, t ABC
输出BANC
解释最小覆盖子串 BANC 包含来自字符串 t 的 A、B 和 C。示例 2
输入s a, t a
输出a
解释整个字符串 s 是最小覆盖子串。示例 3:
输入: s a, t aa
输出:
解释: t 中两个字符 a 均应包含在 s 的子串中
因此没有符合条件的子字符串返回空字符串。提示
m s.length
n t.length
1 m, n 105
s 和 t 由英文字母组成class Solution {public String minWindow(String s, String t) {}
}8.2 做题思路
因为这道题目中说了可以出现重复的字符所以这道题的判断条件就是窗口中是否含有 t 字符串中的所有字符并且窗口中的每个字符出现的次数必须大于 t 字符串中每个字符出现的次数。那么这道题的步骤主要分为两步
在s字符串中找到含有 t 字符串中含有的所有字符的窗口在这个窗口中找长度最小的子串 8.3 Java代码实现
class Solution {public String minWindow(String ss, String tt) {char[] s ss.toCharArray();char[] t tt.toCharArray();int[] hash1 new int[128];int[] hash2 new int[128];int kinds 0;for(char ch : t) {if(hash1[ch] 0) kinds;}int begin -1;int minLen Integer.MAX_VALUE;for(int left 0, right 0,count 0; right s.length; right) {char in s[right];if(hash2[in] hash1[in]) count;while(count kinds) {if(right - left 1 minLen) {begin left;minLen right - left 1;}char out s[left];if(hash2[out]-- hash1[out]) count--;}}if(begin -1) return new String();else return ss.substring(begin,begin minLen);}
}总结
当涉及到解决子串或子数组的问题时滑动窗口算法是一种非常有效的技术。它通过维护一个窗口该窗口在字符串或数组上滑动以解决特定问题。
滑动窗口算法的主要思想是使用两个指针一个指向窗口的起始位置另一个指向窗口的结束位置。通过调整这两个指针可以扩展或收缩窗口以找到所需的解。算法的关键是确定窗口的移动规则以及如何在移动过程中更新解。
下面是滑动窗口算法的一般步骤
初始化窗口的起始指针和结束指针使其指向合理的位置。进入一个循环不断尝试扩展窗口直到窗口无法再扩展为止。在每次窗口移动时更新解如果有必要。如果窗口仍然满足问题的要求尝试收缩窗口以寻找更优的解。重复步骤3和4直到窗口完全收缩并处理完所有元素。
滑动窗口算法的优点是其时间复杂度通常是线性的因为它避免了对每个子串或子数组的重复计算节约了计算资源。它也通常可以在O(1)的空间复杂度下完成。
滑动窗口算法常用于解决一些经典问题例如字符串匹配、子数组和子串求和、最长/最短子数组等。通过适当定义窗口的移动规则和解的更新方式可以针对不同的具体问题进行定制化的实现。
总结而言滑动窗口算法是一种高效的解决子串或子数组问题的方法。它的核心思想是通过维护一个窗口在问题的限定条件下移动窗口的起始和结束指针同时利用解的特性来优化计算过程。使用滑动窗口算法可以提高问题的解决效率并减少不必要的计算。
