【数据结构与算法学习】滑动窗口相关算法题

一、滑动窗口相关概念

1.1 概念

滑动窗口算法可以用以解决数组/字符串的子元素问题，它可以将嵌套的循环问题，转换为单循环问题，降低时间复杂度。

1.1 应用场景的特点

• 需要输出或比较的结果在原数据结构中是连续排列的
• 每次窗口滑动时，只需观察窗口两端元素的变化，无论窗口多长，每次只操作两个头尾元素，当用到的窗口比较长时，可以显著减少操作次数
• 窗口内元素的整体性比较强，窗口滑动可以只通过操作头尾两个位置的变化实现，但对比结果时往往要用到窗口中所有元素

二、算法题

1.1 无重复字符的最长子串[中等]

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

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

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

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

输入: s = ""
输出: 0

//  解题思路：滑动窗口
const lengthOfLongestSubstring = (str) => {
    let tempStr = '';
    let left = 0;
    let right = 0;
    const len = str.length;
    let maxNum = 0;

    while(right < len) {
        right++;
        tempStr = str.substring(left, right);
        const tempLength = tempStr.length;
        // 去重是否长度一致：一致表示无重复字符串
        const isUnique = Array.from(new Set(tempStr)).length === tempLength;
        isUnique && (maxNum = Math.max(maxNum, tempLength));
        (!isUnique) && left++;
    }
    return maxNum;
};

1.2 长度最小的子数组 [中等]

## 描述
给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

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

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

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

//  解题思路：滑动窗口
const minSubArrayLen = (target, nums) => {
    // 初始化滑动窗口左右指针
    let left = 0; 
    let right = 0;
    // 初始化最小长度
    let minSubLen = Infinity;

    while(right <= nums.length && left <= right) {
        const subArr = nums.slice(left, right);
        const sum = subArr.reduce((x, y) => x + y, 0); // 这里比较费时间，可以优化
        if (sum >= target) {
            left++;
            minSubLen = Math.min(minSubLen, subArr.length);
        } else {
            right++;
        }
    }
    return minSubLen ===  Infinity ? 0 : minSubLen;
};
 
// 优化后解法
const minSubArrayLen = (s, nums) => {
  let minLen = Infinity;
  let i = 0;
  let j = 0;
  let sum = 0;
  while (j < nums.length) {   // 主旋律是扩张，找可行解
    sum += nums[j];
    while (sum >= s) {        // 间歇性收缩，优化可行解
      minLen = Math.min(minLen, j - i + 1);
      sum -= nums[i];
      i++;
    }
    j++;
  }
  return minLen === Infinity ? 0 : minLen; // 从未找到可行解，返回0
};

1.3 字符串的排列 [中等]

## 描述
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
换句话说，第一个字符串的排列之一是第二个字符串的 子串 。

输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba")

输入: s1= "ab" s2 = "eidboaoo"
输出: False

const isEqual = (s1, s2) => Array.from(s1).sort().join('') === Array.from(s2).sort().join('');

const checkInclusion = (s1, s2) => {
    const s1Length = s1.length;
    let left = 0;
    let right = s1Length;
    while(right <= s2.length) {
        const tempStr = s2.substring(left, right);
        if (isEqual(tempStr, s1)) {return true;}
        left++;
        right = left + s1Length;
    }
    return false;
};

## 主要使用 hash 去判断窗口和 s1 是否一致，用 sort 太浪费性能了, 上面的方法超时了，用map的方式对比

1.4 最小覆盖子串 【困难】

1.5 滑动窗口最大值 【困难】

## 描述
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

输入：nums = [1], k = 1
输出：[1]

输入：nums = [1,-1], k = 1
输出：[1,-1]

function maxSlidingWindow (nums, k) {
    // 初始化窗口左右指针
    let left = 0;
    let right = k;
    const length = nums.length;
    const result = [];
    while(right <= length) {
        const subArr = nums.slice(left, right);
        result.push(Math.max.apply(null, subArr));
        left++;
        right = left + k;
    };
    return [...result];
};

// 上面的解法超时了

1.6 串联所有单词的子串【困难】

1.7 最小区间

1.8 最小窗口子序列 【会员】

1.9 至多包含两个不同字符的最长子串【会员】