76. 最小覆盖子串

滑动窗口算法的思路是这样：
1、我们在字符串 S 中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引左闭右开区间 [left, right) 称为一个「窗口」。
2、我们先不断地增加 right 指针扩大窗口 [left, right)，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。
3、此时，我们停止增加 right，转而不断增加 left 指针缩小窗口 [left, right)，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同时，每次增加 left，我们都要更新一轮结果。

4、重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头。
这个思路其实也不难，第 2 步相当于在寻找一个「可行解」，然后第 3 步在优化这个「可行解」，最终找到最优解，也就是最短的覆盖子串。左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动，这就是「滑动窗口」这个名字的来历。
下面画图理解一下，needs 和 window 相当于计数器，分别记录 T 中字符出现次数和「窗口」中的相应字符的出现次数。
初始状态：
image.png
image.png
image.png
image.png

之后重复上述过程，先移动 right，再移动 left…… 直到 right 指针到达字符串 S 的末端，算法结束。
如果你能够理解上述过程，恭喜，你已经完全掌握了滑动窗口算法思想。现在我们来看看这个滑动窗口代码框架怎么用：
首先，初始化 window 和 need 两个哈希表，记录窗口中的字符和需要凑齐的字符：

151.翻转字符串里的单词

给定一个字符串，逐个翻转字符串中的每个单词。
示例 1：
输入: “the sky is blue”
输出: “blue is sky the”
示例 2：
输入: “ hello world! “
输出: “world! hello”
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3：
输入: “a good example”
输出: “example good a”
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

思路如下：

  • 移除多余空格
  • 将整个字符串反转
  • 将每个单词反转

举个例子，源字符串为：”the sky is blue “

  • 移除多余空格 : “the sky is blue”
  • 字符串反转：”eulb si yks eht”
  • 单词反转：”blue is sky the”
  1. /**
  2.  * @param {string} s
  3.  * @return {string}
  4.  */
  5.  var reverseWords = function(s) {
  6.    // 字符串转数组
  7.    const strArr = Array.from(s);
  8.    // 移除多余空格
  9.    removeExtraSpaces(strArr);
  10.    // 翻转
  11.    reverse(strArr, 0, strArr.length - 1);
  13.    let start = 0;
  15.    for(let i = 0; i <= strArr.length; i++) {
  16.      if (strArr[i] === ' ' || i === strArr.length) {
  17.        // 翻转单词
  18.        reverse(strArr, start, i - 1);
  19.        start = i + 1;
  20.      }
  21.    }
  23.    return strArr.join('');
  24. };
  26. // 删除多余空格
  27. function removeExtraSpaces(strArr) {
  28.   let slowIndex = 0;
  29.   let fastIndex = 0;
  31.   while(fastIndex < strArr.length) {
  32.     // 移除开始位置和重复的空格
  33.     if (strArr[fastIndex] === ' ' && (fastIndex === 0 || strArr[fastIndex - 1] === ' ')) {
  34.       fastIndex++;
  35.     } else {
  36.       strArr[slowIndex++] = strArr[fastIndex++];
  37.     }
  38.   }
  40.   // 移除末尾空格
  41.   strArr.length = strArr[slowIndex - 1] === ' ' ? slowIndex - 1 : slowIndex;
  42. }
  44. // 翻转从 start 到 end 的字符
  45. function reverse(strArr, start, end) {
  46.   let left = start;
  47.   let right = end;
  49.   while(left < right) {
  50.     // 交换
  51.     [strArr[left], strArr[right]] = [strArr[right], strArr[left]];
  52.     left++;
  53.     right--;
  54.   }
  55. }

28. 实现 strStr()

实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

示例 1: 输入: haystack = “hello”, needle = “ll” 输出: 2
示例 2: 输入: haystack = “aaaaa”, needle = “bba” 输出: -1

说明: 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

KMP的经典思想就是:当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。