带你读《图解算法小抄》二十、滑动窗口（3）

带你读《图解算法小抄》二十、滑动窗口（2）https://developer.aliyun.com/article/1347999?groupCode=tech_library

3.最小长度子数组和

给定一个正整数数组nums和一个正整数target，找出数组中满足其和≥target的最短子数组的长度，如果不存在满足条件的子数组，返回0。

示例：

输入：nums = [2,3,1,2,4,3]，target = 7 输出：2 解释：子数组 [4,3] 的和为 7，且长度最小。

输入：nums = [1,4,4]，target = 4 输出：1 解释：子数组 [4] 的和为 4，且长度最小。

1）题目分析与解题步骤：

这个问题可以使用滑动窗口算法来解决。我们可以维护一个窗口，不断地向右扩展窗口，直到窗口内的元素和≥target。然后，我们尝试将窗口的左边界向右收缩，以寻找更短的满足条件的子数组。

解题步骤如下：

• 初始化两个指针left和right，都指向数组的开始位置。初始化窗口的和windowSum为0，最小子数组的长度minLength为无穷大。
  
• 不断向右移动right指针，扩大窗口。在每次移动时，将当前元素添加到窗口的和windowSum中。
  
• 当窗口的和≥target时，更新最小子数组的长度minLength为当前窗口的大小，并尝试将窗口的左边界向右收缩。
  
• 在收缩窗口时，从窗口的左边界开始，将左边界的元素从窗口的和windowSum中减去，并将左边界向右移动。
  
• 重复步骤2-4，直到right指针到达数组的末尾。
  
• 返回最小子数组的长度minLength。如果不存在满足条件的子数组，返回0。
  

3）JavaScript解题框架：

function minSubArrayLen(nums, target) {
    let left = 0;
    let minLength = Infinity;
    let windowSum = 0;    for (let right = 0; right < nums.length; right++) {
        windowSum += nums[right];        while (windowSum >= target) {
            minLength = Math.min(minLength, right - left + 1);
            windowSum -= nums[left];
            left++;
        }
}
    return minLength === Infinity ? 0 : minLength;
}

在这个框架中，我们使用left和right两个指针来构建窗口，windowSum用于记录窗口内元素的和，minLength记录最小子数组的长度。

我们不断向右移动right指针，将当前元素添加到窗口的和windowSum中。当windowSum≥target时，我们尝试收缩窗口，从窗口的左边界开始，将左边界的元素从windowSum中减去，并将左边界向右移动。在每次收缩窗口时，我们更新最小子数组的长度minLength为当前窗口的大小。

最后，返回minLength作为结果。如果不存在满足条件的子数组，返回0。

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

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

1）问题分析：

这个问题可以通过滑动窗口算法来解决。我们可以使用两个指针，即left和right，来构建和维护一个窗口，确保窗口内的字符不重复。通过不断地移动指针，我们可以找到最长的不含重复字符的子串。

2）解题步骤：

• 初始化两个指针left和right，并初始化最长子串的长度maxLength为0。
  
• 创建一个哈希集合（或者字符数组）set来存储窗口内的字符。哈希集合可以快速判断字符是否出现过。
  
• 使用right指针向右移动，扩大窗口。在每次移动时，检查当前字符是否已经在哈希集合中。
  
• 如果当前字符不在集合中，将其添加到集合中，并更新最长子串的长度maxLength为当前窗口的大小（right - left + 1）。
  
• 如果当前字符已经在集合中，表示遇到了重复字符，需要移动left指针，并将left指针对应的字符从集合中删除，以缩小窗口。重复步骤3，直到right指针达到字符串的末尾。
  

• 返回最长子串的长度maxLength。
  

带你读《图解算法小抄》二十、滑动窗口（4）https://developer.aliyun.com/article/1347996?groupCode=tech_library