【JavaScript】LeetCode：16-20

文章目录

• 16 无重复字符的最长字串
• 17 找到字符串中所有字母异位词
• 18 和为K的子数组
• 19 滑动窗口最大值
• 20 最小覆盖字串

16 无重复字符的最长字串

• 滑动窗口 + 哈希表
• 这里用哈希集合Set()实现。
• 左指针i，右指针j，从头遍历数组，若j指针指向的元素不在set中，则加入该元素，否则更新结果res，删除集合中i指针指向的元素，进入下一轮循环。

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    var sset = new Set();
    var res = 0;
    var j = 0;
    for(var i = 0; i < s.length; i++){
        while(!sset.has(s[j]) && j < s.length){
            sset.add(s[j]);
            j++;
        }
        res = Math.max(res, j - i);
        sset.delete(s[i]);
    }
    return res;
};

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

• 滑动窗口 + 哈希表
• 创建哈希表p_map，记录字符串p中的字符；创建哈希表s_map，记录当前窗口中的字符。
• 窗口左端点：left，窗口右端点：right；结果数组res。
• 移动right指针，直到当前窗口的长度 = t的长度。当某个字符在s_map中的数量 = 该字符在p_map中需要的数量时，need++，即已经有一个字符满足了要求。
• 当need = p_map.size时，所有字符的数量均满足了要求，此时更新结果：将left放入res中；然后移动left指针，缩小窗口，直到窗口中不包含字符串t中的所有字符，即有一个字符的数量不满足要求，就进入下一轮循环，再次移动right指针。

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function(s, p) {
    var p_map = new Map();
    var s_map = new Map();
    for(var item of p){
        p_map.set(item, (p_map.get(item) || 0) + 1);
    }
    var plen = p.length;
    var slen = s.length;
    var res = [];
    var left = 0;
    var need = 0;
    for(var right = 0; right < slen; right++){
        var a = s[right];
        if(p_map.get(a)){
            s_map.set(a, (s_map.get(a) || 0) + 1);
            if(s_map.get(a) == p_map.get(a)){
                need++;
            }
        }
        if(right - left == plen - 1){
            if(need == p_map.size){
                res.push(left);
            }
            var b = s[left];
            left++;
            if(p_map.get(b)){
                if(s_map.get(b) == p_map.get(b)){
                    need--;
                }
                s_map.set(b, s_map.get(b) - 1);
            }
        }
    }
    return res;
};

18 和为K的子数组

• 前缀和 + 哈希表
• sums[i]：以nums[i]为结尾的前缀和。sums[j] - sums[i] = k，sums[j] - k = sums[i]。
• sums[0] = 0，也要将“0：1”放入哈希表。
• 遍历前缀和数组，先查找在哈希表中sums[item] - k的个数，然后再将当前元素放入哈希表中，注意：二者顺序不可调换，否则在k = 0时就会出错，例如[3]，k = 0，若先放入“3：1”，则3 - k = 3 - 0 = 3，此时3的个数为1，结果记录就会 + 1，但其实是错误的。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function(nums, k) {
    var sums = new Array(nums.length + 1).fill(0);
    for(var i = 0; i < nums.length; i++){
        sums[i + 1] = sums[i] + nums[i];
    }
    var map = new Map();
    var res = 0;
    for(var item of sums){
        res += map.get(item - k) || 0;
        map.set(item, (map.get(item) || 0) + 1);
    }
    return res;
};

19 滑动窗口最大值

• 单调队列
• 维护一个从出口到入口单调递减的队列，即出口处是最大值。这里的队列q记录索引值。
• push()、pop()：如果push的元素value大于队列中最后一个元素的数值，那么就将队列最后一个元素弹出，直到push元素的数值小于等于队列最后一个元素的数值为止。
• 从i = k - 1开始记录，max = q[0]所对应的数值。
• i与q[0]所指向的索引相差k时，弹出q[0]。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function(nums, k) {
    var q = [];
    var res = [];
    for(var i = 0; i < nums.length; i++){
        while(q.length != 0 && nums[i] >= nums[q[q.length - 1]]){
            q.pop();
        }
        q.push(i);
        if(i - q[0] == k){
            q.shift();
        }
        if(i >= k - 1){
            res.push(nums[q[0]]);
        }
    }
    return res;
};

20 最小覆盖字串

• 滑动窗口 + 哈希表
• 创建哈希表t_map，记录字符串t中的字符；创建哈希表s_map，记录当前窗口中的字符。
• 窗口左端点：left，窗口右端点：right；当满足条件时的字符串左端点：start，字符串长度：res。
• 移动right指针，直到当前窗口中包含字符串t中的所有字符。当某个字符在s_map中的数量 = 该字符在t_map中需要的数量时，need++，即已经有一个字符满足了要求。
• 当need = t_map.size时，所有字符的数量均满足了要求，此时更新结果：左端点start和字符串长度res；然后移动left指针，缩小窗口，直到窗口中不包含字符串t中的所有字符，即有一个字符的数量不满足要求，就进入下一轮循环，再次移动right指针。

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function(s, t) {
    if(s.length < t.length){
        return "";
    }
    var s_map = new Map();
    var t_map = new Map();
    for(var item of t){
        t_map.set(item, (t_map.get(item) || 0) + 1);
    }
    var need = 0;
    var left = 0;
    var start = 0;
    var res = Number.MAX_VALUE;
    for(var right = 0; right < s.length; right++){
        var a = s[right];
        if(t_map.has(a)){
            s_map.set(a, (s_map.get(a) || 0) + 1);
            if(s_map.get(a) == t_map.get(a)){
                need++;
            }
        }
        while(need == t_map.size){
            var b = s[left];
            if(right - left + 1 < res){
                start = left;
                res = right - left + 1;
            }
            left++;
            if(t_map.has(b)){
                if(s_map.get(b) == t_map.get(b)){
                    need--;
                }
                s_map.set(b, s_map.get(b) - 1);
            }
        }
    }
    return (res == Number.MAX_VALUE)? "": s.slice(start, start + res);
};