#1024程序员节#征文
目录
1.滑动窗口的定义
2.算法实战
2.1 长度最小的子数组
算法思路
2.2 无重复字符的最长子串
算法思路
2.3 最大连续 1 的个数 III
算法思路
哈希表的简要补充
结束语
祝大家1024程序节快乐！！！
1.滑动窗口的定义
滑动窗口是一种双指针算法的特例，主要用于处理连续区间的问题，特别是在字符串或数组上寻找满足某些条件的连续子区间。在滑动窗口中，通常有两个指针，分别称为“窗口的起始指针”和“窗口的结束指针”，它们一起构成一个“窗口”，在数组或字符串上移动。
滑动窗口的几个关键特点
1.动态调整大小：窗口的大小和位置会根据问题的需求动态地调整。
2.连续性：窗口内的元素是连续的。
3.方向性：窗口通常从数组的左端开始，向右移动。
滑动窗口算法的步骤
- 初始化两个指针，通常称为`left`和`right`，它们分别表示窗口的起始和结束位置。
- 移动`right`指针来扩展窗口，直到窗口中的元素满足某个条件。
- 当窗口满足条件后，尝试通过移动`left`指针来缩小窗口，同时保持窗口中的元素满足条件。
- 在移动指针的过程中，更新所需的答案（例如最大或最小长度）。
简而言之，可以理解成两个指针的同向移动。
滑动窗口算法常用于以下典型问题：
- 最长不含重复字符的子字符串：在字符串中找到一个最长子串，该子串不包含任何重复字符。
- 最小覆盖子串：在字符串S中找到一个包含字符串T中所有字符的最短连续子串。
2.算法实战
2.1 长度最小的子数组
209. 长度最小的子数组 - 力扣（LeetCode）
算法思路
1.暴力枚举(超时）
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
// 记录结果
int ret = INT_MAX;
int n = nums.size();
// 枚举开始位置
for (int start = 0; start < n; start++)
{
int sum = 0; // 记录从这个位置开始的连续数组的和
// 寻找结束位置
for (int end = start; end < n; end++)
{
sum += nums[end]; // 将当前位置加上
if (sum >= target) // 当这段区间内的和满⾜条件时
{
// 更新结果，start 开头的最短区间已经找到
ret = min(ret, end - start + 1);
break;
}
}
}
// 返回最后结果
return ret == INT_MAX ? 0 : ret;
}
};补充：将ret赋值无穷大，即=INT_MAX
2.滑动窗口解法
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
//sort(nums.begin(),nums.end());
int len=INT_MAX,n=nums.size();
int sum=0;
// int left=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++];
}
}
return len==INT_MAX?0:len;
}
};2.2 无重复字符的最长子串
3. 无重复字符的最长子串 - 力扣（LeetCode）
算法思路
1.暴力枚举
首先在暴力枚举的过程中，可以通过哈希表来记录字符出现的次数，简单来说，就是定义一个数组，每个字符对应的ASCII值是数组的相应位置。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n=s.size(),ret=0,i,j;
for( i=0;i<n;i++){
int hash[128]={0};
for( j=i;j<n;j++){
hash[s[j]]++;
if(hash[s[j]]>1)
break;
}
ret=max(ret,j-i);
}
return ret;
}
};当字符字数大于一的时候，就跳出内循环，更新结果，更改数组首元素。
2.滑动窗口
在暴力枚举的过程中，我们发现当进行新的一层外循环时，只要还在遇到重复字母的范围内，就会重复遍历相同的子串子集，并且长度是减小的。
所以我们可以省略这些操作，让滑动窗口满足：窗口内所有元素都是不重复的。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n=s.size();
int left=0,right=0,ret=0;
int hash[128]={0};
while(right<n){
hash[s[right]]++;//进入窗口
while(hash[s[right]]>1){//判断
hash[s[left]]--;
left++;}//出窗口
//ret=max(ret,(right-1)-(left-1)+1);
ret=max(ret,right-left+1);//更新结果
right++;//下一个元素进入窗口
}
return ret;
}
};2.3 最大连续 1 的个数 III
1004. 最大连续1的个数 III - 力扣（LeetCode）
算法思路
1.暴力枚举（超时）
用两个循环嵌套，固定首数组元素，然后遍历，枚举出所有情况。定义一个count来储存0的数量。
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int n=nums.size();
int i,j,len=0;
for(i=0;i<n;i++){
int count=0;
for(j=i;j<n;j++){
if(nums[j]==0)
count++;
if(count>k){
break;
}
len=max(len,j-i+1);
}
}
return len;
}
};2.滑动窗口
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int len=0,zero=0;
for(int left=0,right=0;right<nums.size();right++){
if(nums[right]==0) zero++;
while(zero>k){
if(nums[left++]==0){
zero--;
}
}
len=max(len,right-left+1);
}
return len;
}
};算法采用双指针技术来维护一个窗口，该窗口包含最多 k个0。通过调整窗口的左右边界，我们可以找到包含最多1的子数组。
算法步骤
1. 初始化变量：
- len：记录当前找到的最长子数组的长度。
- zero：记录当前窗口中0的数量。
- left和 right：分别表示滑动窗口的左右边界。
2. 遍历数组：
- 使用 right指针遍历数组 nums。
- 如果 `nums[right]` 是0，则增加 zero计数。
3. 调整窗口大小：
- 当 zero的数量超过 k 时，表示窗口中的0太多，需要通过增加 left 指针来缩小窗口，直到窗口中的0的数量不大于 k。
- 在增加 left指针的过程中，如果 nums[left] 是0，则减少 zero计数。
4. **更新最长子数组长度**：
- 在每次调整窗口后，计算当前窗口的长度（`right - left + 1`），并与 len比较，更新 len为最大值。
5. 返回结果：
- 遍历完成后，返回 len 作为结果，它表示最长的连续1的子数组的长度，同时允许最多 k 个0。
哈希表的简要补充
哈希表（Hash table），也被称作散列表，是一种数据结构，用于存储键值对，并能够实现快速查找。哈希表通过一个哈希函数来计算每个键的哈希值，哈希值决定了在表中的位置。
以下是哈希表的一些关键特性：
1. 哈希函数：哈希表使用哈希函数将键映射到表中一个位置来存储对应的值。理想的哈希函数应该容易计算，并且能够将不同的键均匀分布到哈希表中。
2. 冲突解决：由于哈希函数可能会将不同的键映射到同一个位置，这种情况称为“冲突”。解决冲突的方法有多种，比如链地址法（在同一位置存储多个元素，形成一个链表），开放寻址法（寻找下一个空位置）等。
3. 查找效率：在理想情况下，哈希表的查找、插入和删除操作的时间复杂度可以达到O(1)。然而，在最坏的情况下（例如，所有键都映射到同一个位置），这些操作的时间复杂度可能会退化到O(n)。
4. 动态扩容：当哈希表中的元素数量达到一定比例时，哈希表可能会进行扩容，以维持操作的效率。扩容通常涉及创建一个更大的表，并将所有现有元素重新哈希到新表中。
5. 负载因子：负载因子是哈希表中元素数量与哈希表大小的比例。通常，当负载因子超过某个阈值时，哈希表会进行扩容。
结束语
本篇博客就到此结束啦，后面还会更新该算法的相关题目，也会更多有趣的算法陆续产出，感谢友友们一路来的支持！！！
