【JavaScript】LeetCode：16-20

本文主要是介绍【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);
};