牛客题霸 NC28 最小覆盖子串

痛定思痛。 2022-09-11 04:09 180阅读 0赞

https://www.nowcoder.com/practice/c466d480d20c4c7c9d322d12ca7955ac

# 解决方案 #

## Go ##

### 版本一 ###

func minWindow(S string, T string) string { 
    	// write code here
    	left, right := 0, 0             //表示窗口左右位置的指针
    	start := 0                      //start 表示最后结果字符串开始位置
    	var minLen int = 1e9            // minlen表示最后字符串长度，二者可以表示一个字符串
    	var need = make(map[byte]int)   //need的存放字符串T的所有字符统计
    	var window = make(map[byte]int) //window 存放现有的窗口中出现在need中的字符统计
    	match := 0                      //window与need的匹配度
    	for _, v := range T { 
    		need[byte(v)]++
    	}
    
    	for right < len(S) { 
    		for match < len(need) && right < len(S) { 
    			c1 := S[right]
    			if _, ok := need[c1]; ok { 
    				window[c1]++
    				if window[c1] == need[c1] { 
    					match++
    				}
    			}
    			right++
    		}
    		for match == len(need) { 
    			//当匹配度等于need,说明这段区间可以作为候选结果，更新ret
    			if right-left < minLen { 
    				minLen = right - left
    				start = left
    			}
    			c2 := S[left]
    			if _, ok := need[c2]; ok { 
    				window[c2]--
    				if window[c2] < need[c2] { 
    					match--
    				}
    			}
    			left++
    		}
    	}
    	if minLen == 1e9 { 
    		return ""
    	} else { 
    		return S[start : start+minLen]
    	}
    }

# 参考文章 #

发表评论取消回复

表情：

评论列表（有 0 条评论，180人围观）

还没有评论，来说两句吧...

相关阅读

相关牛客题霸 NC1 大数加法

https://www.nowcoder.com/practice/11ae12e8c6fe48f883cad618c2e81475 解决方案 Java

缺乏、安全感/ 2023年01月17日 04:42/ 0 赞/ 191 阅读

相关牛客题霸 NC30 数组中未出现的最小正整数

解决方案 Go 版本一 func minNumberdisappered(arr []int) int { // write code h

傷城~/ 2022年09月11日 04:10/ 0 赞/ 137 阅读

相关牛客题霸 NC28 最小覆盖子串

https://www.nowcoder.com/practice/c466d480d20c4c7c9d322d12ca7955ac 解决方案 Go 版本一

痛定思痛。/ 2022年09月11日 04:09/ 0 赞/ 180 阅读

相关牛客题霸 NC27 集合的所有子集

https://www.nowcoder.com/practice/c333d551eb6243e0b4d92e37a06fbfc9 解决方案 Go 版本一

╰半橙微兮°/ 2022年09月11日 04:09/ 0 赞/ 169 阅读

相关牛客题霸 NC26 括号生成

https://www.nowcoder.com/practice/c9addb265cdf4cdd92c092c655d164ca 解决方案 Go 版本一

朴灿烈づ我的快乐病毒、/ 2022年09月11日 04:09/ 0 赞/ 151 阅读

相关牛客题霸 NC23 划分链表

https://www.nowcoder.com/practice/1dc1036be38f45f19000e48abe00b12f 解决方案 Go fu

港控/mmm°/ 2022年09月06日 04:51/ 0 赞/ 160 阅读

相关牛客题霸 NC19 子数组的最大累加和问题

https://www.nowcoder.com/practice/554aa508dd5d4fefbf0f86e5fe953abd 解决方案 Go fu

朱雀/ 2022年09月05日 04:08/ 0 赞/ 145 阅读

相关牛客题霸 NC17 最长回文子串

https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6 解决方案 Go Manach

约定不等于承诺〃/ 2022年09月03日 12:22/ 0 赞/ 172 阅读

相关牛客题霸 NC7 买卖股票的最好时机

https://www.nowcoder.com/practice/64b4262d4e6d4f6181cd45446a5821ec 解决方案 Go fu

你的名字/ 2022年09月03日 10:24/ 0 赞/ 145 阅读

相关牛客题霸 NC2 重排链表

https://www.nowcoder.com/practice/3d281dc0b3704347846a110bf561ef6b 解决方案 Go fu

骑猪看日落/ 2022年09月03日 10:24/ 0 赞/ 178 阅读