滑动窗口算法（思想）

我不是女神ヾ 2023-06-24 04:59 36阅读 0赞

# 滑动窗口算法（思想） #

**题目：**

*输入: "abcabcbb"*  
*输出: 3*   
*解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。*

子串和串中字符的对比，只要出现相同字符都算重复，肯定要用到嵌套循环。如果暴力枚举，每个长度的子串都拿出来做自检，时间复杂度会比较高。使用滑动窗口的思想，对错误信息进行合理利用，可以有效减少执行次数。

C语言解法：

int lengthOfLongestSubstring(char * s){     
        int i = 0, j = 0;     int maxlen = 0;     int curlen = 0;     
        int len = strlen(s);     
        if (len == 0)         return 0;     
        for (; j < len && len - i > maxlen; j++) {         
            curlen++;         
            for (int k = i; k <= j; k++) {             
                if (s[k] == s[j + 1]) {                 
                    if (curlen > maxlen)                     maxlen = curlen; 
                    i = k + 1;                 
                    curlen = j - i + 1;                 
                    break;             
                }         
            }     
        }         
        if (curlen > maxlen)         return curlen;     
        else         return maxlen; 
    }

滑动窗口初听觉得抽象模糊，其实拿卷尺一对比很好理解  
一个字符串，要在里面找出最长且没有重复字符的子串，就像拿着卷尺在上面不停地缩拉测量  
子串就是这个卷尺的伸出部分，即一个窗口，左边缩进，右边拉出  
因为不能有重复的字符，在右端逐渐拉长的过程中，每新增加的一个新字符都要拿来和左侧子串中的字符做对比  
在上面的程序里，用 i 指向卷尺头部，用 j 指向卷尺尾部，k 则作为子串中字符的索引  
每次对比开始时，用 i 的值初始化 k，当找到重复字符时，又将 k + 1的值赋给 i，即直接将窗口的左侧移动到重复字符的下一个字符位置  
与枚举法相比，由于利用了子串中重复字符的位置，直接将窗口左侧跳到该字符的下一个位置，每次检查出重复减少了 k - i 个子串的自检

**题目**

*给定数组，获取数组中n个连续元素最大的和*

C语言解法：

int maxSumSub(nums, n) { 
        int len = (int) sizeof(nums) / sizeof(int);  
        int maxsum = 0; 
        if (n > len) {  return 0;   }  
        for (int i = 0; i < n; i++) {  maxsum += nums[i];    } 
        int windowsum = maxsum; 
        for (int i = n; i < len; i++) {
            windowsum += nums[i] - nums[i - n]; 
            if (windowsum > maxsum)  maxsum = windowsum; 
       } 
        return maxsum; 
    }

如果用滑动窗口法，基本思想是，每次向右滑动时，窗口右侧进入的新元素减去左侧退出的旧元素，得到的结果与上次的和相加得到新的和  
这样做的巧妙之处在于，无论题设n有多大，每次窗口移动后，计算新和，只需将窗口两端进出的新旧元素相减，得到的结果与旧和相加就可以得到新和  
**总结**  
上述两个题目，分别用到了动态滑动窗口和固定滑动窗口，即在滑动时长度变化和不变的两种窗口  
可以看到，滑动窗口的应用场景有几个特点：  
1. 需要输出或比较的结果在原数据结构中是连续排列的（字符串中的连续不重复子串，数组中的连续元素最大和）  
2. 每次窗口滑动时，只需观察窗口两端元素的变化，无论窗口多长，每次只操作两个头尾元素，当用到的窗口比较长时，可以显著减少操作次数  
3. 窗口内元素的整体性比较强，窗口滑动可以只通过操作头尾两个位置的变化实现，但对比结果时往往要用到窗口中所有元素（检查窗口中是否含有重复字符，对比窗口中元素的和）