原文：76. 最小覆盖子串(leetcode 解题) - 每天一个JavaScript小知识@Js中文网 · 码农进阶题库

原文地址：https://www.javascriptc.com/interview-tips/zh_cn/leetcode/leetcode-javascript-solution-076/

题目：

难度：Hard

相关话题：哈希表、双指针、字符串、Sliding Window

给定一个字符串 S 和一个字符串 T，请在 S 中找出包含 T 所有字母的最小子串。

示例：

输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"

说明：

  • 如果 S 中不存这样的子串，则返回空字符串 "" 。

  • 如果 S 中存在这样的子串，我们保证它是唯一的答案。

思路：

首先对t的字母建立count，以出现频率作为它的值，由于题目没有明确说明大小写，因此设定128位。

变量tLen表示t的长度；

变量preID表示当前一个滑动区间的最左侧的索引；

变量start和end表示最小区间的左索引和右索引。

遍历s，

如果count[s.charCodeAt(i)]-->0，说明s[i]属于t，需要tLen--；

如果tLen===0，说明t中的值已经全部在区间[preID,i]出现了，比较区间[preID,i]和[start,end]，如果更小，更新[start,end]；

检查count[s.charCodeAt(preID++)]++==0，如果条件成立，说明preID索引刚好调整到跳过1个存在t中的字母，并且这个字母当前已经不存在与[preID,i]区间内。

遍历完毕后，返回区间[start,end]，如果不存在，则返回''。

/**
 * @来源： Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍：一个致力于帮助开发者用代码改变世界为使命的平台，每天都可以在这里找到技术世界的头条内容
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function(s, t) {
  let count=Array(128).fill(0)
  let tLen=t.length
  for(let w of t){
    let code=w.charCodeAt(0)
    count[code]++
  }
  // console.log(count)
  let preID=0,start=0,end=Infinity,curLen=0
  for(let i=0;i<s.length;i++){
    if(count[s.charCodeAt(i)]-->0){
      tLen--
    }
    while(tLen===0){
      if(i-preID<end-start){
        end=i+1
        start=preID
      }
      if(count[s.charCodeAt(preID++)]++==0) tLen++
    }
  }
  return end===Infinity?'':s.substring(start,end)
};

扩展阅读：