带你读《图解算法小抄》二十、滑动窗口(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