文章目录 16 无重复字符的最长字串 17 找到字符串中所有字母异位词 18 和为K的子数组 19 滑动窗口最大值 20 最小覆盖字串
16 无重复字符的最长字串
滑动窗口 + 哈希表 这里用哈希集合Set()实现。 左指针i,右指针j,从头遍历数组,若j指针指向的元素不在set中,则加入该元素,否则更新结果res,删除集合中i指针指向的元素,进入下一轮循环。
javascript">
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指针。
javascript">
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,但其实是错误的。
javascript">
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]。
javascript">
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指针。
javascript">
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) ;
} ;