本文共 3015 字，大约阅读时间需要 10 分钟。

从LeetCode上的一道题说起

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。示例: 输入: s = 7, nums = [2,3,1,2,4,3]输出: 2解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。

看到这个题，我不知道大家是怎么想的，我想到的就是暴力解法：

1、从头开始，以每个数字作为结果数组的头，找到刚好能大于s的结果数组。并记下结果数组中 [1:] 的和（Python写法），记为 t 。 2、如果 t 已经大于 s 了，那就结果数组头开始递减，一直减到 t 刚好小于 s 为止。 3、时刻保留一个最短子序列。 4、结果数组往后遍历一格，将值加入 t 当中。 5、回到第二步，直到结果序列的屁股顶到原序列的末位。 6、返回保留的最短子序列 的长度。

---

这是暴力解法吧，不知道为什么他们要叫这种解法为滑动窗口，还给出了不低的难度系数。。

如果看不懂我上面的表述，可以看图：（一图胜千言）

---

通过归纳，我们可以勾勒出滑动窗口法的大体框架（只是基本框架，根据不同的问题应适当变动，重在把握精神）

初始化窗口端点L，R，一般L为0，R为1    初始化最优值    while R < len(Array):        while R < len(Array):            R += 1              #移动右端点            if R < len(Array):                更新状态                    if 状态满足条件:                可选的更新最优值的位置                break           #一旦满足条件即跳出        if R == len(Array):     # 若循环是由于移动到数组末尾结束，则停止整个程序。因为之后已经不再有可能的解            break        while L < R:            更新状态    # 移动左端点，需要更新状态            L += 1            if 状态满足条件：                可选的更新最优值的位置            else：  # 一旦窗口所在区间不再满足条件即跳出，去移动右端点                break        可选的对于L，R端点的后续处理    return 最优值

---

继续看题，今天不聊天。

无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: "abcabcbb"

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

示例 2:

输入: "bbbbb"

输出: 1解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: "pwwkew"

输出: 3解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

思路：

这道题主要用到思路是：滑动窗口

什么是滑动窗口？ 其实就是一个队列,比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！

如何移动？

我们只要把队列的左边的元素移出就行了，直到满足题目要求！ 一直维持这样的队列，找出队列出现最长的长度时候，求出解！ 时间复杂度：O(n)

代码实现：

class Solution {
   public:    int lengthOfLongestSubstring(string s) {
           if(s.size() == 0) return 0;        unordered_set
   
     lookup;        int maxStr = 0;        int left = 0;        for(int i = 0; i < s.size(); i++){
               while (lookup.find(s[i]) != lookup.end()){
                   lookup.erase(s[left]);                left ++;            }            maxStr = max(maxStr,i-left+1);            lookup.insert(s[i]);    }        return maxStr;            }};
   

---

无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

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

示例 2:

输入: “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3:

输入: “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。

思路：

这道题主要用到思路是：滑动窗口

什么是滑动窗口？ 其实就是一个队列,比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！

如何移动？

我们只要把队列的左边的元素移出就行了，直到满足题目要求！ 一直维持这样的队列，找出队列出现最长的长度时候，求出解！ 时间复杂度：O(n)

代码实现：

class Solution {
   public:    int lengthOfLongestSubstring(string s) {
           if(s.size() == 0) return 0;        unordered_set
   
     lookup;        int maxStr = 0;        int left = 0;        for(int i = 0; i < s.size(); i++){
               while (lookup.find(s[i]) != lookup.end()){
                   lookup.erase(s[left]);                left ++;            }            maxStr = max(maxStr,i-left+1);            lookup.insert(s[i]);    		}        return maxStr;    }};
   

---

多说无益，精练才是王道。

转载地址：https://lion-wu.blog.csdn.net/article/details/113953769 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！