动态中的守候：滑动窗口与距离的诗篇

标签：诗篇 字符 守候 窗口 right 滑动 我们 hash left

公主请阅

• 1. 长度最小的子数组
• • 1.1 题目说明
  • • 示例 1
    • 示例 1
    • 示例 2
    • 示例 3
  • 1.2 题目分析
  • 1.3 代码部分
  • 1.4 代码分析
• 2. 无重复字符的最长子串
• • 2.1 题目说明
  • • 示例 1
    • 示例 1
    • 示例 2
    • 示例 3
  • 2.2 题目分析
  • 2.3 代码部分
  • 2.4 代码分析
  • 2.5 代码深度分析

1. 长度最小的子数组

题目传送门

---

1.1 题目说明

根据你提供的图片，题目是**“长度最小的子数组”**（Leetcode 209 题），具体信息如下：

示例 1

题目描述：
给定一个含有 n 个正整数的数组 nums 和一个正整数 target，要求找到满足其总和大于或等于 target 的长度最小的连续子数组，并返回其长度。如果不存在这样的子数组，返回 0。

示例 1

• 输入：
  • target = 7
  • nums = [2, 3, 1, 2, 4, 3]
• 输出：2
• 解释：子数组 [4, 3] 是该条件下的长度最小的子数组。

示例 2

• 输入：
  • target = 4
  • nums = [1, 4, 4]
• 输出：1

示例 3

• 输入：
  • target = 11
  • nums = [1, 1, 1, 1, 1, 1, 1, 1]
• 输出：0

要求：
找到符合条件的最小长度子数组，如果不存在，返回 0。

---

1.2 题目分析

在数组中找到子数组，里面的元素内容加起来大于等于7，然后返回这个子数组的最小的长度

解法一：暴力枚举出所有的子数组的和，时间复杂度是n^3

解法二：利用单调性，使用‘同向双指针’来进行优化操作

两个指针朝着一个方向移动

同向双指针被称为滑动窗口

滑动窗口的使用方法：

1.先定义两个指针
我们的left先不要动，持续进窗口right，直到我们的Sum的大小大于我们的target的值

这个sum伴随着right的移动一直在更新

当right到这个位置我们的sum就大于target了

这个题的话我们找到数组中大于等于7的子数组就行了，并且返回我们的子数组的长度

这个时候我们需要更新我们此时的子数组的长度，就是4

然后我们就可以进行出窗口的操作了，移动left

此时的left指向了3的位置，那么我们就需要对这个Sum进行一个更新的操作了

然后我们进行一个判断的操作，这个sum<7,所以我们继续进行进窗口的操作，right往右边进行移动

然后此时我们的sum=10>7符合要求了

我们就更新这个长度

然后我们继续进行出窗口的操作

此时的sum=7，并且长度更新为3

更新完结果之后我们继续进行出窗口的操作

left继续往右边进行移动

此时的sum=6<7

然后我们的right进窗口的操作

然后我们更新内容
最后我们继续循环内容，left出窗口到4这个位置，然后我们的sum=7，并且len更新到了2
直到我们的指针没有下一个元素指向了，那么我们的滑动窗口就结束了

我们的这个滑动窗口利用了单调性规避了很多没有必要的枚举行为

时间复杂度:

使用right进窗口的时候我们是需要一个循环的

---

1.3 代码部分

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums)
    {
        int n=nums.size(),sum=0,len=INT_MAX;//用sum来标记我们的和，len标记我们的长度
        for(int left=0,right=0;right<n;right++)//我们的right一直在望右边进行移动的操作
        {
            //进入窗口
            sum+=nums[right];
            while(sum>=target)//当我们的结果大于我们的目标值的时候，我们进行更新的操作
            {
                //我们对这个len进行一个更新的操作，每次更新出最小的len的大小
                len=min(len,right-left+1);//因为这个是下标我们需要进行一个加一的操作

                //出窗口的操作
                //我们先对sum进行一个更新的操作，left望右边移动了，那么更新的sum就需要将left指向的数删除了
                sum-=nums[left++];//这里我们并且进行这个left++的操作

                //这里我们就完成了判断，更新结果以及出窗口的操作
                //然后这个循环结束之后我们继续进行判断的操作
            }
        }
        return len==INT_MAX?0:len;//如果len的结果还是初始化的时候的值，那么我们就返回一个0，否则的话就将len进行返回的操作
    }
};

---

1.4 代码分析

我们先计算当前数组的长度，利用size()，然后定义一个变量sum来标记我们的和，以及一个变量len进行标记我们的长度，初始化为INT_MAX
然后我们利用for循环进行数组的遍历操作，条件是right<n我们就停止，因为我们的right一直往右边进行移动的操作
然后我们进入窗口，将right指向的数据累加到sum里面
然后进行一个while循环进行后续的判断操作，循环的条件是·sum·大于等于我们要找打值，只要我们的结果大于我们的目标值的时候，我们进行更新的操作
我们对当前的len进行一个更新的操作，更新最小的长度，
然后我们进行下一组的判断操作，我们就进行了一个出窗口的操作，然后我们对sum进行一个更新的操作，因为出窗口，我们将left当前的元素从累加的sum中进行删除的操作，然后我们让left进行加加的操作，然后我们就继续进行后面的循环操作，直到我们的right越界了循环就停止了，那么我们的最小长度的子数组我们就找到了，然后我们将这个len进行一个返回的操作，如果len还是初始化的时候，那么我们就返回一个0就行了，否则的话我们直接将我们遍历完数组之后的len进行返回就行了

---

2. 无重复字符的最长子串

题目传送门

2.1 题目说明

示例 1

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

示例 1

• 输入：
  • s = "abcabcbb"
• 输出：3
• 解释：无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2

• 输入：
  • s = "bbbbb"
• 输出：1
• 解释：无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3

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

要求：
找到不含重复字符的最长子串的长度。

2.2 题目分析

解法一：暴力枚举+哈希表（判断字符是否重复出现）：

• 找到一个子串，里面的元素是不重复的，我们直接将所有的子串都列举出来，以某一个位置为起点向后进行枚举，当我们枚举到后面发现重复的元素的时候我们直接停下来，以这个字符开头的子串那么我们只能枚举到这里了，然后我们将所有的情况都枚举到，然后找到子串长度的最大值

最坏的情况是我们的时间复杂度是n^2级别的，当我们在判断的时候我们从头看到尾都没有重复的，但是我们仍在遍历操作

解法二：利用规律，使用滑动窗口来解决问题
那么我们的暴力解法是否存在优化的情况呢？

我们定义left指向我们的第一个元素，然后定义right定义到我们的开始为止，然后进行遍历看看我们最远能到哪里，然后我们创建一个哈希表来帮助我们保存这段字符的信息

我们每次进行right的遍历，我们会判断当前的字符在不在哈希表里面，不在的话就将当前字符丢进去，如果我们right在遍历的时候然后对当前字符判断在不在哈希表里面，如果在的话我们就停止我们的枚举操作，那么这个长度就是我们Left到right的长度了

我们此时的开始位置是d，结束位置是这个a

那么我们的第一组就结束了，我们让Left往右走，继续进行新的一组子串的判断操作了

那么我们的right就要从上组的位置回到left的位置了

那么我们开始进行第二组的操作，然后我们发现我们的right的位置又跑到了a的位置停下了，因为在前面我们已经有了一个a了，那么这里就是重复了

就是说我们在我们框的这个串里面，不管从哪里开头，我们撑死到下个a就结束了

那么我们就没有必要判断中间的子串了

不管Left到哪里，这个right撑死到第二个a的位置，那么当Left在第一个位置的时候就是最长的在当前

那么我们是可以让left跳过字符a继续进行判断操作的，那么我们的right就被解放往后面进行移动了

所以总结：当我们发现区间里面有重复字符的话，我们让left跳过这个重复字符,接下来再继续进行操作，那么我们的right就不用回来了，因为我们已经跳过了这个重复字符了，说明当前的Left和right区间之间是不存在重复字符的

那么到这里，总结解法二：

解法二：利用规律，使用滑动窗口来解决问题

• 先定义left和right充当我们的左端点和右端点

• 进窗口 让字符进入哈希表

• 判断 当窗口内存在重复字符时候，（根据判断结果是否出窗口）执行出窗口（从哈希表中国杀出该字符就完成了出窗口的操作），让left移动

• 更新结果（在整个判断结束之后）

2.3 代码部分

class Solution {
public:
    int lengthOfLongestSubstring(string s)
    {
        int hash[128]={0};//使用数组模拟哈希表
        int left=0,right=0,n=s.size();
        int ret=0;//记录结果，即最长子串长度
        while(right<n)
        {
            //将当前字符计数器+1
            hash[s[right]]++;//进入窗口,当前字母在哈希表出现的次数
            //  如果当前字符在窗口中出现多于一次
            while(hash[s[right]]>1)//判断条件
            {
                hash[s[left]]--;//出窗口
                left++;
            }
            //更新结果
            ret=max(ret,right-left+1);
            right++;//让下一个元素进入窗口
        }
        return ret;
    }
};

---

2.4 代码分析

我们先创建一个数组来模拟哈希表
然后我们创建left和right两个指针，然后计算我们的数组元素个数
然后定义一个变量ret进行记录结果，即最长的子串的长度
接下来我们就进行遍历数组进行下面的操作
利用while循环进行遍历数组，遍历条件就是我们的right不能超过n造成越界的情况
在循环里面我们利用哈希表记录当前的字符的出现次数，出现了我们就进行加加的操作，这个相当于计数器
如果哪个数出现了大于1次的话，我们就利用这个while循环进行出窗口的操作，如果right的值仍然是大于1的话，我们就持续进行出窗口的操作
那么就是我们让当前的left位置上的数减减，然后让left进行加加操作，往右边接着走
出了内部循环的话，我们就进行更新当前的结果，更新当前的ret的最大值
然后进行right++让right往右边接着走
最后我们出了循环，我们直接将ret进行返回的操作就行了
这个就是最终我们的最长的子串的长度了

---

2.5 代码深度分析

理解两个 while 循环中哈希表（hash 数组）的作用需要从滑动窗口的机制出发。我们从两个方面来解释：扩展窗口和收缩窗口。

哈希表的作用

hash[128] 是一个大小为 128 的数组，用来记录窗口中每个字符的出现次数。每个字符的 ASCII 码是一个整数，数组的索引是字符对应的 ASCII 值，值是这个字符在窗口中出现的次数。

第一个 while 循环（主循环）：扩展窗口

while (right < n) {
    hash[s[right]]++; // 将当前字符加入窗口，并增加其出现的次数

• 这里 right 是窗口的右边界，遍历字符串时，right 指向的字符会逐个进入窗口。

• hash[s[right]]++ 表示将 right 指向的字符加入窗口，更新该字符在哈希表中的出现次数。

比如，假设字符串是 "abcabcbb"，在开始时，right 指向 "a"，哈希表会更新 hash['a'] = 1，表示 'a' 在当前窗口中出现了一次。

第二个 while 循环：收缩窗口

while (hash[s[right]] > 1) {
    hash[s[left]]--; // 收缩窗口，移除左边界字符
    left++; // 左指针右移
}

• 如果 hash[s[right]] > 1，说明当前窗口中的 s[right] 这个字符已经出现了多次，即出现了重复字符。此时就需要通过移动左指针来缩小窗口，直到这个重复字符被移出窗口。

• hash[s[left]]-- 表示将窗口左边界 left 指向的字符移出窗口，减少该字符在哈希表中的出现次数。

详细解释哈希表的作用

假设我们有一个字符串 "abcabcbb"，我们看下如何一步步处理：

1. 初始状态：

• left = 0, right = 0

• hash 数组初始为 0，即所有字符在窗口中的计数都为 0。

2. 第一次扩展窗口：

• right 指向 "a"，哈希表记录 hash['a'] = 1。窗口此时为 "a"，没有重复字符，继续扩展。

• right++，指向 "b"，hash['b'] = 1，窗口为 "ab"，无重复，继续扩展。

• right++，指向 "c"，hash['c'] = 1，窗口为 "abc"，无重复，继续扩展。

3. 发现重复字符：

• right++，再次指向 "a"，hash['a']++，此时 hash['a'] = 2，表示 "a" 出现了两次。

• 因为出现了重复字符，所以进入内层的 while 循环。此时需要通过移动 left 来缩小窗口：

  1. hash['a']--，left++，将 "a" 移出窗口，窗口变为 "bc"，此时 hash['a'] = 1，不再有重复字符，退出内层 while 循环。

4. 继续扩展：

• right++，指向 "b"，hash['b']++，此时 hash['b'] = 2，重复字符 "b" 再次出现。

• 进入内层 while，通过移动 left，把窗口左边的 "b" 移除，直到窗口中没有重复字符。

这样不断调整窗口的大小，确保窗口中没有重复字符，并计算最长子串的长度。

总结哈希表的工作机制

• hash 数组的作用是在滑动窗口内实时记录每个字符的出现次数。每当字符加入窗口时，哈希表相应位置的值会递增，当字符被移出窗口时，哈希表相应位置的值会递减。

• 第一个 while 循环通过右指针不断扩展窗口，每次把一个新字符加入窗口，并更新哈希表。

• 第二个 while 循环则通过左指针缩小窗口，直到窗口内没有重复字符为止。这时，哈希表的作用是帮助我们检测是否有重复字符，并在有重复字符时调整窗口。

这就是两个 while 循环中哈希表的主要逻辑。

我们来一步步分析**"pwwkew"**这个例子，看看代码如何处理。

初始状态：

• left = 0, right = 0，窗口为空，hash[128] = {0}。

• ret = 0（记录当前最大子串的长度）。

步骤 1：右指针移动到 "p"

• right = 0，指向字符 "p"，此时 hash['p']++，即 hash['p'] = 1。

• 窗口内没有重复字符，当前子串为 "p"，长度为 1。

• 更新结果：ret = max(0, 0 - 0 + 1) = 1。

步骤 2：右指针移动到 "w"

• right = 1，指向字符 "w"，hash['w']++，即 hash['w'] = 1。

• 窗口内没有重复字符，当前子串为 "pw"，长度为 2。

• 更新结果：ret = max(1, 1 - 0 + 1) = 2。

步骤 3：右指针再次移动到 "w"

• right = 2，再次指向 "w"，hash['w']++，即 hash['w'] = 2，表示 "w" 出现了两次，窗口内出现了重复字符。

• 进入内层 while 循环，因为 hash['w'] > 1：

  1. hash['p']--，left++，将左边的 "p" 移出窗口，窗口变为 "ww"，hash['p'] = 0。

  2. hash['w']--，left++，将第一个 "w" 移出窗口，窗口变为 "w"，hash['w'] = 1。

• 退出内层 while 循环，此时窗口恢复无重复状态，子串为 "w"，长度为 1，但结果不更新，因为 1 < ret。

步骤 4：右指针移动到 "k"

• right = 3，指向字符 "k"，hash['k']++，即 hash['k'] = 1。

• 窗口内没有重复字符，当前子串为 "wk"，长度为 2。

• 更新结果：ret = max(2, 3 - 2 + 1) = 2（结果保持不变）。

步骤 5：右指针移动到 "e"

• right = 4，指向字符 "e"，hash['e']++，即 hash['e'] = 1。

• 窗口内没有重复字符，当前子串为 "wke"，长度为 3。

• 更新结果：ret = max(2, 4 - 2 + 1) = 3。

步骤 6：右指针移动到 "w"

• right = 5，再次指向字符 "w"，hash['w']++，即 hash['w'] = 2，表示 "w" 又出现了两次，窗口内再次出现重复字符。

• 进入内层 while 循环，因为 hash['w'] > 1：

  1. hash['w']--，left++，将窗口的第一个 "w" 移出，窗口变为 "ke"，hash['w'] = 1。

• 退出内层 while 循环，窗口恢复无重复状态，子串为 "kew"，长度为 3。

• 更新结果：ret = max(3, 5 - 3 + 1) = 3（结果保持不变）。

最终结果：

经过上述步骤，整个字符串遍历完成，最长的无重复子串是 "wke" 或 "kew"，长度为 3。

详细过程总结：

5. p: 子串 "p"，长度 1。

6. pw: 子串 "pw"，长度 2。

7. ww: 重复，缩小窗口到 "w"，长度 1。

8. wk: 子串 "wk"，长度 2。

9. wke: 子串 "wke"，长度 3。

10. kew: 子串 "kew"，长度 3。

最终得到的最长无重复子串的长度是 3。

标签：诗篇,字符,守候,窗口,right,滑动,我们,hash,left
From： https://blog.csdn.net/2301_80863610/article/details/143093303