经典滑动窗口试题（一）

📘北尘_：个人主页
🌎个人专栏:《Linux操作系统》《经典算法试题 》《C++》 《数据结构与算法》

☀️走在路上，不忘来时的初心

---

一、将x减到0的最小操作数

1、题目讲解

2、讲解算法原理

3、代码实现

class Solution {
public:int minOperations(vector<int>& nums, int x) {int n=nums.size(),ret=0,sum=0,target,len=-1;for(int i=0;i<n;i++)ret+=nums[i];target=ret-x;if(target<0)  return -1;for(int left=0,right=0;right<n;right++){sum+=nums[right];while(sum>target)sum-=nums[left++];if(sum==target)len=max(len,right-left+1);}if(len==-1) return len;else return n-len;}
};

---

二、无重复的最长子串

1、题目讲解

2、讲解算法原理

3、代码实现

class Solution {
public:int lengthOfLongestSubstring(string s) {int n=s.size();int count[128]={0},len=0;for(int left=0,right=0;right<n;right++){count[s[right]]++;while(count[s[right]]==2)count[s[left++]]--;len=max(len,right-left+1);}return len;}
};

---

三、最大连续为1的个数

1、题目讲解

2、讲解算法原理

3、代码实现

class Solution {
public:int longestOnes(vector<int>& nums, int k) {int n=nums.size(),zero=0,len=0;for(int left=0,right=0;right<n;right++){if(nums[right]==0) zero++;while(zero>k)if(nums[left++]==0) zero--;}return len;}
};

---

四、长度最小的子数组

1、题目讲解

2、讲解算法原理

3、代码实现

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums){int n=nums.size(),len=INT_MAX;int sum=0;for(int left=0,right=0;right<n;right++){sum+=nums[right];while(sum>=target){len=min(len,right-left+1);sum-=nums[left];left++;}}return len==INT_MAX?0:len;}
};

---