牛客题霸 NC28 最小覆盖子串

痛定思痛。 2022-09-11 04:09 213阅读 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 条评论，213人围观）

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

相关阅读

相关 NC28 最小覆盖子串

> [牛客华为机试题库【题号 HJ开头】（重点看）][HJ] > [牛客在线编程算法篇【题号NC开头】][NC] > [剑指offer【题号 JZ开头】][offer_

电玩女神/ 2024年03月27日 17:07/ 0 赞/ 77 阅读

相关最小覆盖子串

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。示例：输入: S = "ADOBECODEBANC", T = "ABC"

矫情吗；*/ 2023年02月11日 13:29/ 0 赞/ 18 阅读

相关牛客题霸 NC1 大数加法

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

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

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

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

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

相关牛客题霸 NC26 括号生成

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

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

相关牛客题霸 NC23 划分链表

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

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

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

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

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

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

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

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

相关牛客题霸 NC10 大数乘法

https://www.nowcoder.com/practice/c4c488d4d40d4c4e9824c3650f7d5571 解决方案 JAVA

比眉伴天荒/ 2022年09月03日 12:17/ 0 赞/ 51 阅读

相关牛客题霸 NC2 重排链表

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

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