什么是滑动窗口？就是一个队列,然后通过在这个队列中的各种移除和添加满足题目需求
题目:
209. 长度最小的子数组 - 力扣（LeetCode）
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int left = 0;
int sum = 0;
int n = nums.length;
int ret = n+1;
for(int i = 0;i<n;i++){
sum+=nums[i];
while(sum-nums[left] >= target){
sum= sum-nums[left++];
}
if(sum>=target){
ret = Math.min(ret,i-left+1);
}
}
return ret<=n?ret:0;
}
}复杂度分析
时间复杂度：O(n)
空间复杂度：O(1)
713. 乘积小于 K 的子数组 - 力扣（LeetCode）
class Solution {
public int numSubarrayProductLessThanK(int[] nums, int k) {
//滑动窗口
//l r
//[l,r] [l+1,r]...[r,r]
//r-1+1
if(k<=1){
return 0;
}
int n = nums.length,ans = 0,prod = 1,left = 0;
for(int right = 0;right<n;++right){
prod *= nums[right];
while(prod>=k){
prod/=nums[left++];
}
ans+=right-left+1;
}
return ans;
}
}本题采用的是双指针滑动窗口，大循环是右指针的移动，内部小循环是左指针的移动。
时间复杂度：O(n)，其中 n 是数组 nums 的长度，右指针遍历一遍数组，左指针紧随其后最多遍历一遍数组；
空间复杂度：O(1)，只创建了有限的几个常量变量作为记录。
1004. 最大连续1的个数 III - 力扣（LeetCode）
滑动窗口 + 变量计数模板
class Solution {
public int slidingWindow(int[] nums, int k) {
//数组/字符串长度
int n = nums.length;
//双指针，表示当前遍历的区间[left, right]，闭区间
int left = 0, right = 0;
//定义变量统计 子数组/子区间 是否有效
int sum = 0;
//定义变量动态保存最大 求和/计数
int res = 0;
//右指针遍历到数组尾
while (right < n) {
//增加当前右指针对应的数值
sum += nums[right];
//当在该区间内 sum 超出定义范围
while (sum > k) {
//先将左指针指向的数值减去
sum -= nums[left];
//左指针右移
left++;
}
//到 while 结束时，我们找到了一个符合题意要求的 子数组/子串
res = Math.max(res, right - left + 1);
//移动右指针，去探索下一个区间
right++;
}
return res;
}
}
class Solution {
public int longestOnes(int[] nums, int k) {
int n = nums.length;
int left = 0;
int right = 0;
int zeros = 0;
int len=0;
while(right<n){
if(nums[right]==0){
zeros++;
}
//当0个数超了,让left一直右移到满足
while(zeros>k){
if(nums[left]==0){
zeros--;
}
left++;
}
//记录符合条件的长度
len = Math.max(len,right-left+1);
right++;
}
return len;
}
}567. 字符串的排列 - 力扣（LeetCode）
72ms
class Solution {
public boolean checkInclusion(String s1, String s2) {
if (s1.length() > s2.length()) {
return false;
}
int[] count1 = new int[26];
// 统计s1中每个字符出现的次数
for (int i = 0; i < s1.length(); i++) {
char c = s1.charAt(i);
count1[c - 'a']++;
}
// 定义滑动窗口的范围是[l,r]，闭区间，长度与s1相等
int l = 0, r = s1.length();
while (r <= s2.length()) {
// 统计窗口s2[l,r-1]内的元素出现的次数
int[] count2 = new int[26];
for (int i = l; i < r; i++) {
char c = s2.charAt(i);
count2[c - 'a']++;
}
// 如果滑动窗口内各个元素出现的次数跟 s1 的元素出现次数完全一致，返回 True
if(Arrays.equals(count1,count2)) {
return true;
}
l++;
r++;
}
return false;
}
}效率很低23ms
class Solution {
public boolean checkInclusion(String s1, String s2) {
//getOrDefault（Object key, Object defaultValues)
//若map中存在key 则返回key对应的value值
//否则返回默认值defaultValues
//滑动窗口 + 两哈希,始终保证窗口长度,当长度超了,左指针准备右移
Map<Character,Integer>need = new HashMap<>();
Map<Character,Integer>map = new HashMap<>();
//创建[双指针] 和 [有效变量]
int left = 0,right = 0;
int valid = 0;
for(Character c:s1.toCharArray()){
need.put(c,need.getOrDefault(c,0)+1);
}
while(right<s2.length()){
char c = s2.charAt(right);
if(need.containsKey(c)){
map.put(c,map.getOrDefault(c,0)+1);
if(need.get(c).equals(map.get(c))){
valid++;
}
}
//当凑齐了元素,还要判断长度
while(right-left+1>=s1.length()){
if(valid==need.size()){
return true;
}
char d = s2.charAt(left);
if(need.containsKey(d)){
if(need.get(d).equals(map.get(d))){
valid--;
}
map.put(d,map.get(d)-1);
}
left++;
}
right++;
}
return false;
}
}6ms
#define MAX_CHAR_LENGTH 26
bool isMatch(int*hash1,int *hash2)
{
for(int i = 0;i<MAX_CHAR_LENGTH;i++){
if(hash1[i]!=hash2[i])return false;
}
return true;
}
bool checkInclusion(char* s1, char* s2) {
if(strlen(s1)>strlen(s2))return false;
int len1 = strlen(s1);
int len2 = strlen(s2);
int windowSize = len1;
int hash1[MAX_CHAR_LENGTH];
int hash2[MAX_CHAR_LENGTH];
memset(hash1,0,sizeof(hash1));
memset(hash2,0,sizeof(hash2));
//初始化hash1,hash2
for(int i = 0;i<windowSize;i++){
hash1[s1[i]-'a']++;
hash2[s2[i]-'a']++;
}
//首次匹配
if(isMatch(hash1,hash2))return true;
//s2的滑动窗口,每次右移一位,更新hash2
for(int i = len1;i<len2;i++){
hash2[s2[i]-'a']++;
hash2[s2[i-len1]-'a']--;
if(isMatch(hash1,hash2))return true;
}
return false;
}5ms
class Solution {
public boolean checkInclusion(String s1, String s2) {
int n = s1.length(),m = s2.length();
if(n>m){
return false;
}
int[] cnt1 = new int[26];
int[] cnt2 = new int[26];
for(int i =0;i<n;i++){
++cnt1[s1.charAt(i)-'a'];
++cnt2[s2.charAt(i)-'a'];
}
if(Arrays.equals(cnt1,cnt2)){
return true;
}
for(int i=n;i<m;i++){
++cnt2[s2.charAt(i)-'a'];
--cnt2[s2.charAt(i-n)-'a'];
if(Arrays.equals(cnt1,cnt2)){
return true;
}
}
return false;
}
}
3. 无重复字符的最长子串 - 力扣（LeetCode）
import java.util.HashMap;
/**
* <h2>无重复字符的最长子串</h2>
* <p>1.给定一个字符串s,请你找出其中不含有重复字符的最长子串的长度.</p>
* <p>2.s由英文字母,数字,符号和空格组成</p>
*/
public class Leetcode03 {
public int lengthOfLongestSubstring(String s){
HashMap<Character,Integer> map = new HashMap<>();//key返回比较大用hashMap 但是这道题目仅仅是128个字符可以用数组
int begin = 0;
int maxLength = 0;
for(int end = 0;end<s.length();end++){
char ch = s.charAt(end);
if (map.containsKey(ch)) {//重复时,调整begin
begin = Math.max(begin,map.get(ch) + 1);//防止begin回退
map.put(ch,end);
}else{//没有重复
map.put(ch,end);
}
// System.out.println(s.substring(begin,end+1));
maxLength = Math.max(maxLength,end - begin +1);
}
return maxLength;
}
public static void main(String[] args){
// System.out.println(new Leetcode03().lengthOfLongestSubstring("abcabcbb"));
Leetcode03 e02 = new Leetcode03();
// System.out.println(e02.lengthOfLongestSubstring("abcabcbb"));
System.out.println(e02.lengthOfLongestSubstring("abba"));
/*
[(a,0),(b,2)]
b
e
abba
*/
/*
a
ab
abc
bca
cab
abc
cb
b
*/
/*
给定一个字符串 s ,请你找出其中不含重复字符的最长子串的长度
abcabcbb 3
a
ab
abc
bca
cab
abc
cb
b
bbbbbb 1
b
pwwkew 3
p
pw
w
wk
wke
kew
[(a,3),(b,7),(c,5)]
b
e
abcabcbb
要点:
1.用 begin 和 end 表示子串开始和结束位置
2.用hash表检查重复字符
3.从左到右查看每一个字符,如果:
- 没遇到重复字符,调整end
- 遇到重复的字符,调整begin
- 将当前字符放入hash表
4.end - begin + 1 是当前子串长度
*/
}
}
76. 最小覆盖子串 - 力扣（LeetCode）
16ms
class Solution {
public String minWindow(String S, String t) {
//这道题目大写小写都有直接创建128大小的数组,保证所有ASCII字符都可以统计
char[] s = S.toCharArray();
int m = s.length;
int ansLeft = -1;
int ansRight=m;
int left = 0;
int[] cntS =new int[128];//s子串字母出现次数
int[] cntT = new int[128];//t中字母出现次数
for(char c:t.toCharArray()){
cntT[c]++;
}
for(int right =0;right<m;right++){//移动子串右端点
cntS[s[right]]++;//右端点字母移入子串
while(isCovered(cntS,cntT)){//涵盖
if(right-left<ansRight-ansLeft){//找到更短的子串
ansLeft = left;
ansRight =right;
}
cntS[s[left++]]--;//左端点字母移出子串
}
}
return ansLeft<0?"":S.substring(ansLeft,ansRight+1);
}
private boolean isCovered(int[] cntS,int[] cntT){
for(int i ='A';i<='Z';i++){
if(cntS[i] < cntT[i]){
return false;
}
}
for(int i ='a';i<='z';i++){
if(cntS[i] < cntT[i]){
return false;
}
}
return true;
}
}13ms
class Solution {
public String minWindow(String s, String t) {
// 参数校验
if (s == null || t == null || s.length() < t.length()) {
return "";
}
// 保存t字符出现的次数，表示每个字符待需要的数量
Map<Character, Integer> tMap = new HashMap<>(t.length());
for (int i = 0; i < t.length(); i++) {
tMap.put(t.charAt(i), tMap.getOrDefault(t.charAt(i), 0) + 1);
}
// 判断窗口是否包含了t的所有元素，避免每次去遍历tMap，增加耗时
int needCnt = t.length();
// 定义最小结果集时的左右边界，初始化边界长度为最大值
int[] minResult = new int[]{0, Integer.MAX_VALUE};
int length = s.length();
// 定义滑动窗口左右边界，右边界开始移动
for (int i = 0, j = 0; j < length; j++) {
char c = s.charAt(j);
// 包含t，待需要的数量减一
if (tMap.getOrDefault(c, 0) > 0) {
needCnt--;
}
// 同时map需要的字符数量减一
tMap.put(c, tMap.getOrDefault(c, 0) - 1);
// 都包含了，此时右边界j不动，开始移动左边界，尝试缩小窗口
if (needCnt == 0) {
while (true) {
c = s.charAt(i);
// 左边界字符已经满足了，不再需要了，则退出循环，没办法继续缩小了
// 否则继续缩小，那么会执行下面的+1，所需要的字符又增加了
if (tMap.get(c) == 0) {
break;
}
// 左边界字符
// map还有多余数量可以缩小
// 缩小左边界，该字符所需要的数量+1
tMap.put(c, tMap.getOrDefault(c, 0) + 1);
i++;
}
// 左边界也更新完了，这时该更新结果了,覆盖res
if (j - i < minResult[1] - minResult[0]) {
minResult[1] = j;
minResult[0] = i;
}
c = s.charAt(i);
//将左边界右移,执行下一个窗口
// 由于左边界是t需要的字符，右移后，需要更新tMap和needCnt，表示还需要增加一个字符
tMap.put(c, tMap.getOrDefault(c, 0) + 1);
needCnt++;
i++;
}
}
// 超过边界，返回空串
if (minResult[1] > length) {
return "";
} else {
return s.substring(minResult[0], minResult[1] + 1);
}
}
}
