vps网站如何绑定多个域名,微商城小程序商城,带管理后台的网站,旅游网站建设成本核算接上文滑窗基础题#xff1a;滑动窗口算法 - LC3 无重复字符的最长子串-CSDN博客#xff0c;介绍了滑窗的基础题目和滑窗解法模板#xff0c;这次带来滑窗进阶题解。
76. 最小覆盖子串
困难
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果…接上文滑窗基础题滑动窗口算法 - LC3 无重复字符的最长子串-CSDN博客介绍了滑窗的基础题目和滑窗解法模板这次带来滑窗进阶题解。
76. 最小覆盖子串
困难
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串则返回空字符串 。
这道进阶题其实不算难但细节拉满漏掉一处都无法通过我将解题的关键点都注释在代码中。 func minWindow(s string, t string) string {need : make(map[byte]int)window : make(map[byte]int)for i : 0; i len(t); i {need[t[i]]}valid : 0 //用来记录window中寻找到到满足覆盖t中的字符的个数start, end : 0, math.MaxInt32 //初始化找到的覆盖子串的左右指针l, r : 0, 0 // 初始化左右指针for r len(s) {//滑窗模板 先动右指针c : s[r]rif need[c] 0 { //这个if是为了只处理t中出现的字符串减少运算也可省去window[c]if window[c] need[c] {valid //如果c字符在两个map里出现次数相同那么说明合法的覆盖字符又多个一个}}//达到滑窗收缩的条件valid为算法记录的合法覆盖字符数量len(need)为所有需要覆盖的字符数量for valid len(need) {//收缩前先取当前覆盖子串的长度更新最小长度if r-l end-start {start lend r}//滑窗模板 移动左指针d : s[l]lif need[d] 0 { //这个if是为了只处理t中出现的字符串减少运算也可省去if window[d] need[d] {valid-- //左指针即将向后移动字符d的合法覆盖将不再满足valid--}window[d]--}}}if end math.MaxInt32 {return }return s[start:end]
}
这里有个点可能会有人有疑问因为字符串切片是包头不包尾的即end所在的index是不会被截取的为什么覆盖子串字符串的是s[start:end]而不是s[start:end1]
这是因为我们在外层更新右指针r的for循环里每次进入循环前先直接更新了右指针r也就是说r已经被提前推到下一个索引位置了。假设把r放到整个for循环的最后那么endr就可以改成endr1like this
for r len(s) {//滑窗模板 先动右指针c : s[r]if need[c] 0 { //这个if是为了只处理t中出现的字符串减少运算也可省去window[c]if window[c] need[c] {valid //如果c字符在两个map里出现次数相同那么说明合法的覆盖字符又多个一个}}//达到滑窗收缩的条件valid为算法记录的合法覆盖字符数量len(need)为所有需要覆盖的字符数量for valid len(need) {//收缩前先取当前覆盖子串的长度更新最小长度if r-l end-start {start lend r 1}//滑窗模板 移动左指针d : s[l]lif need[d] 0 { //这个if是为了只处理t中出现的字符串减少运算也可省去if window[d] need[d] {valid-- //左指针即将向后移动字符d的合法覆盖将不再满足valid--}window[d]--}}r}
