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

简介: 带你读《图解算法小抄》二十、滑动窗口(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。然后,我们尝试将窗口的左边界向右收缩,以寻找更短的满足条件的子数组。

 

解题步骤如下:

 

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

3JavaScript解题框架:

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

 

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

 

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

 

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


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


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

 

 

1问题分析:

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

2解题步骤:

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

 

  • 返回最长子串的长度maxLength


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

相关文章
|
3月前
|
算法
【算法】滑动窗口——最大连续1的个数
【算法】滑动窗口——最大连续1的个数
|
6月前
|
算法 测试技术 C++
【动态规划】【滑动窗口】【C++算法】 629K 个逆序对数组
【动态规划】【滑动窗口】【C++算法】 629K 个逆序对数组
|
6月前
|
机器学习/深度学习 算法
【优选算法】—— 滑动窗口类问题
【优选算法】—— 滑动窗口类问题
100 0
|
3月前
|
算法
【算法】滑动窗口——最小覆盖子串
【算法】滑动窗口——最小覆盖子串
|
3月前
|
算法
【算法】滑动窗口——找到字符串中所有字母异位词
【算法】滑动窗口——找到字符串中所有字母异位词
|
3月前
|
算法
【算法】滑动窗口——将x减到0的最小操作数
【算法】滑动窗口——将x减到0的最小操作数
|
3月前
|
算法
【算法】滑动窗口——无重复字符的最长子串
【算法】滑动窗口——无重复字符的最长子串
|
3月前
|
算法
【算法】滑动窗口——长度最小的子数组
【算法】滑动窗口——长度最小的子数组
|
3月前
|
算法 容器
【算法】滑动窗口——串联所有单词的子串
【算法】滑动窗口——串联所有单词的子串
|
3月前
|
算法
【算法】滑动窗口——水果成篮
【算法】滑动窗口——水果成篮