76. 最小覆盖子串

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function(s, t) {
    let light = 0;
    let right = 0;
    // 需要的子串及字符个数
    const need = new Map();
    for (let c of t) {
        need.set(c, need.has(c) ? need.get(c) + 1 : 1);
    }
    let needTypeCount = need.size; // 需求中不同字符总个数
    let minSub = '';
    while(right < s.length){
        const current = s[right];
        if (need.has(current)) {
            // 需要对应字符个数减1
            need.set(current, need.get(current) - 1);
            if (need.get(current) === 0) {
                needTypeCount--;
            }
        }
        // 完全满足t字符串的子串了，尝试尽可能减小子串的长度
        while(needTypeCount === 0) {
            const mewMinSub = s.substring(light, right + 1); // 左闭右开
            // 找到最小子串   
            // 优化：minSub最开始是空字符串无需逻辑判断，到下一轮再比较长度
            if (!minSub || mewMinSub.length < minSub.length) {
                minSub = mewMinSub;
            }
            const currentLight = s[light]; 
            // 移动左指针对应字符在需求列表中，对应字符需求数加1（子串减少一个目标字符，就有一个需求量的增加）
            if (need.has(currentLight)) {
                need.set(currentLight, need.get(currentLight) + 1);
                if (need.get(currentLight) === 1) {
                    needTypeCount++;
                }
            }
            light++;
        }
        right++;
    }
    return minSub;
};

209.长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
示例：
输入：s = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。

var minSubArrayLen = function(target, nums) {
    // 长度计算一次
    const len = nums.length;
    let l = r = sum = 0, 
        res = len + 1; // 子数组最大不会超过自身
    while(r < len) {
        sum += nums[r++];
        // 窗口滑动
        while(sum >= target) {
            // r始终为开区间 [l, r)
            res = res < r - l ? res : r - l;
            sum-=nums[l++];
        }
    }
    return res > len ? 0 : res;
};

567. 字符串的排列

var checkInclusion = function(s1, s2) {
    let result = false

    let freq = {}
    for (const item of s1) {
        freq[item] = freq[item] ? ++freq[item] : 1
    }

    const nLen = Object.keys(freq).length

    let left = 0
    let right = 0
    let matchCount = 0
    while (right < s2.length) {
        const curR = s2[right]
        right++
        if (--freq[curR] === 0) {
            matchCount++
        }
        while (matchCount === nLen) {
            if (right - left === s1.length) {
                return true
            }
            const curL = s2[left]
            left++
            if (++freq[curL] > 0) {
                matchCount--
            }
        }
    }

    return result
};

438. 找到字符串中所有字母异位词

var findAnagrams = function (s, p) {
  let left = 0
  let right = 0
  let freq = {}
  let count = 0
  let result = []

  for (const item of p) {
    freq[item] = freq[item] ? ++freq[item] : 1
  }

  const nLen = Object.keys(freq).length

  while (right < s.length) {
    const curR = s[right]
    right++

    if (--freq[curR] === 0) {
      count++
    }

    // 收窄
    while (count === nLen) {
      if (right - left === p.length) {
        result.push(left)
      }
      const curL = s[left]
      left++
      if (++freq[curL] > 0) {
        count--
      }
    }

  }

  return result
}

最长无重复子串

var lengthOfLongestSubstring = function (s) {
  let result = 0

  let left = 0
  let right = 0
  let freq = {}
  while (right < s.length) {
    const curR = s[right]
    right++
    freq[curR] = freq[curR] ? ++freq[curR] : 1

    while (freq[curR] > 1) {
      const curL = s[left]
      left++
      freq[curL]--
    }
    result = Math.max(right - left, result)
  }
  return result
}

数据结构与算法

滑动窗口

76. 最小覆盖子串

209.长度最小的子数组

567. 字符串的排列

438. 找到字符串中所有字母异位词

最长无重复子串