1.长度最小的子数组
（1）题目描述
给定一个含有
n个正整数的数组和一个正整数target。找出该数组中满足其总和大于等于
target的长度最小的 子数组[numsl, numsl+1, ..., numsr-1, numsr]，并返回其长度。如果不存在符合条件的子数组，返回0。
（2）原理
如何把暴力解法优化为滑动窗口
解法一:暴力枚举出所有的子数组的和
解法二：滑动窗口-时间复杂度O(n)【暴力解法遇到单调性时】
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int left=0,right=0;
int n=nums.length;
int count=0;
int len=Integer.MAX_VALUE;
int sumsum=0;
for(left=0,right=0;right<n;right++){
//进窗口
sumsum=sumsum+nums[right];
while(sumsum>=target){
len=Math.min(len,right-left+1);
//出窗口
sumsum=sumsum-nums[left];
left++;
}
}
return len==Integer.MAX_VALUE?0:len;
}
}2. 无重复字符的最长子串
LCR 016. 无重复字符的最长子串 - 力扣（LeetCode）
（1）题目描述
子串的子数组都是连续的一串
给定一个字符串
s，请你找出其中不含有重复字符的 最长子串
的长度。示例 1:
输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。示例 2:
输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。示例 3:
输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke"是一个子序列，不是子串。
（2）原理
解法一:暴力枚举 + 哈希表(判断字符是否重复出现)
解法二：利用规律，使用滑动窗口
class Solution {
public static int lengthOfLongestSubstring(String s) {
int left=0,right=0,n=s.length();
int len=0;
if(n<=1){
return n;
}
HashSet<Character> hashSet=new HashSet<>();
for(left=0,right=0;right<n;right++){
char exsitss=s.charAt(right);
while(hashSet.contains(exsitss)){
//出窗口
hashSet.remove(s.charAt(left));
left++;
}
//进窗口
hashSet.add(exsitss);
len=Math.max(len,right-left+1);
}
return len;
}
}同时我们可以用数组模拟哈希表
3.最大连续1的个数3
1004. 最大连续1的个数 III - 力扣（LeetCode）
给定一个二进制数组
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）题目描述
（2）原理
解法一：暴力枚举+zero计数器
解法二：滑动窗口
class Solution {
public int longestOnes(int[] nums, int k) {
int left=0,right=0,n=nums.length;
int count=0;
int lenlen=0;
for(left=0,right=0;right<n;right++){
//进窗口
if(nums[right]==0){
count++;
}
//出窗口
while(count>k){
if(nums[left]==0){
count--;
}
left++;
}
lenlen=Math.max(lenlen,right-left+1);
}
return lenlen;
}
}4.将x减到0的最小操作数
（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 。
（2）原理
正难则反
class Solution {
public int minOperations(int[] nums, int x) {
//正难则反
int left=0,right=0,n=nums.length;
int sum=0;
int sumsum=0;
int len=Integer.MIN_VALUE;
for(int i=0;i<n;i++){
sum=sum+nums[i];
}
int target=sum-x;
if(target==0){
return n;
}
//滑动窗口
for(left=0,right=0;right<n;right++){
sumsum=sumsum+nums[right];
while(sumsum>=target&&left<=right){
if(sumsum==target){
len=Math.max(len,right-left+1);
}
//出窗口
sumsum=sumsum-nums[left];
left++;
}
}
return len==Integer.MIN_VALUE?-1:(n-len);
}
}5.水果成篮
（1）题目描述
你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组
fruits表示，其中fruits[i]是第i棵树上的水果 种类 。你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：
- 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
- 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
- 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
给你一个整数数组
fruits，返回你可以收集的水果的 最大 数目。
（2）原理
转化:找出一个最长的子数组的长度，子数组中不超过两种类型的水果
解法一：暴力枚举+哈希表
解法二：滑动窗口
class Solution {
public int totalFruit(int[] fruits) {
int n = fruits.length;
Map<Integer, Integer> cnt = new HashMap<Integer, Integer>();
int left = 0, ans = 0;
for (int right = 0; right < n; ++right) {
cnt.put(fruits[right], cnt.getOrDefault(fruits[right], 0) + 1);
while (cnt.size() > 2) {
cnt.put(fruits[left], cnt.get(fruits[left]) - 1);
if (cnt.get(fruits[left]) == 0) {
cnt.remove(fruits[left]);
}
++left;
}
ans = Math.max(ans, right - left + 1);
}
return ans;
}
}Java HashMap getOrDefault() 方法 | 菜鸟教程 (runoob.com)
6.找出字符串所有字母异位词
（1）题目描述
LCR 015. 找到字符串中所有字母异位词 - 力扣（LeetCode）
给定两个字符串
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" 的变位词。
（2）原理
滑动窗口是固定的情况
class Solution {
public List<Integer> findAnagrams(String ss, String pp) {
List<Integer> ret=new ArrayList<>();
char[] s=ss.toCharArray();
char[] p=pp.toCharArray();
int[] hash1=new int[26];//统计字符串p，每一个字符出现的个数
for(char ch:p){
hash1[ch-'a']++;
}
int[] hash2=new int[26];//统计窗口中，每一个字符出现的个数
int m=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为有效字符
count++;
}
if(right-left+1>m){//出窗口，
char out=s[left++];
if(hash2[out-'a']--<=hash1[out-'a']){//出窗口+维护
count--;
}
}
//更新结果
if(count==m){
ret.add(left);
}
}
return ret;
}
}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"] 顺序排列的连接。
（2）原理
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> ret=new ArrayList<>();
Map<String,Integer> hash1=new HashMap<>();//保存字典中的所有字频
for(String str:words){
hash1.put(str,hash1.getOrDefault(str,0)+1);
}
int len=words[0].length(),m=words.length;//每个字符串长度是一致的
for(int i=0;i<len;i++){//执行操作
//滑动窗口的具体操作
Map<String,Integer> hash2=new HashMap<>();//保存窗口中的所有字频
for(int left=i,right=i,count=0;right+len<=s.length();right+=len){
//进窗口+维护
String in=s.substring(right,right+len);
hash2.put(in,hash2.getOrDefault(in,0)+1);
if(hash2.get(in)<=hash1.getOrDefault(in,0)){
count++;
}
//出窗口
if(right-left+1>len*m){
//出窗口+维护
String out=s.substring(left,left+len);
if(hash2.get(out)<=hash1.getOrDefault(out,0)){
count--;
}
hash2.put(out,hash2.get(out)-1);
left+=len;
}
//更新结果
if(count==m){
ret.add(left);
}
}
}
return ret;
}
}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.lengthn == t.length1 <= m, n <= 105s和t由英文字母组成
（2）原理
合法的时候才出窗口
class Solution {
public String minWindow(String ss, String tt) {
char[] s=ss.toCharArray();
char[] t=tt.toCharArray();
int[] hash1=new int[128];//统计字符串t中字符的频次
int kinds=0;//字符串t中，有多少种字符
for(char ch:t){
if(hash1[ch]++==0){
kinds++;
}
}
int[] hash2=new int[128];//统计滑动窗口字符的频次
int minlen=Integer.MAX_VALUE,begin=-1;
for(int left=0,right=0,count=0;right<s.length;right++){
char in=s[right];
if(++hash2[in]==hash1[in]){
count++;//进窗口+维护count
}
while(kinds==count){//判断
//更新结果
if(right-left+1<minlen){
begin=left;
minlen=right-left+1;
}
char out=s[left++];
if(hash2[out]--==hash1[out]){
count--;//出窗口+维护count
}
}
}
if(begin==-1){
return new String();
}else{
return ss.substring(begin,begin+minlen);
}
}
}本站资源均来自互联网，仅供研究学习，禁止违法使用和商用，产生法律纠纷本站概不负责！如果侵犯了您的权益请与我们联系！
转载请注明出处： 免费源码网-免费的源码资源网站 » 2.优化算法之滑动窗口1
发表评论 取消回复