算法魅力-双指针之滑动窗口的叛逆

#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;
    }
};

算法思路

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;
    }
};

哈希表的简要补充

哈希表（Hash table），也被称作散列表，是一种数据结构，用于存储键值对，并能够实现快速查找。哈希表通过一个哈希函数来计算每个键的哈希值，哈希值决定了在表中的位置。

以下是哈希表的一些关键特性：
1. 哈希函数：哈希表使用哈希函数将键映射到表中一个位置来存储对应的值。理想的哈希函数应该容易计算，并且能够将不同的键均匀分布到哈希表中。
2. 冲突解决：由于哈希函数可能会将不同的键映射到同一个位置，这种情况称为“冲突”。解决冲突的方法有多种，比如链地址法（在同一位置存储多个元素，形成一个链表），开放寻址法（寻找下一个空位置）等。
3. 查找效率：在理想情况下，哈希表的查找、插入和删除操作的时间复杂度可以达到O(1)。然而，在最坏的情况下（例如，所有键都映射到同一个位置），这些操作的时间复杂度可能会退化到O(n)。
4. 动态扩容：当哈希表中的元素数量达到一定比例时，哈希表可能会进行扩容，以维持操作的效率。扩容通常涉及创建一个更大的表，并将所有现有元素重新哈希到新表中。
5. 负载因子：负载因子是哈希表中元素数量与哈希表大小的比例。通常，当负载因子超过某个阈值时，哈希表会进行扩容。

结束语

本篇博客就到此结束啦，后面还会更新该算法的相关题目，也会更多有趣的算法陆续产出，感谢友友们一路来的支持！！！

祝大家1024程序节快乐！！！