网站备案信息的核查方式,做平面的网站,宝格丽官网,做网站哪家强题目
无重复字符最长子串 给定一个字符串 s #xff0c;请你找出其中不含有重复字符的 最长子串 的长度。
题解
func lengthOfLongestSubstring(s string) int {m : make(map[uint8]int)res : 0for l, r : 0, 0; r len(s); r {m[s[r]]if v, ok : m[s[r]]; !ok || v 1…题目
无重复字符最长子串 给定一个字符串 s 请你找出其中不含有重复字符的 最长子串 的长度。
题解
func lengthOfLongestSubstring(s string) int {m : make(map[uint8]int)res : 0for l, r : 0, 0; r len(s); r {m[s[r]]if v, ok : m[s[r]]; !ok || v 1 {length : r - l 1if length res {res length}} else {for s[l] ! s[r] {m[s[l]]--l}m[s[l]]--l}}return res}核心细节一 使用滑动窗口寻找合适子串
首先我们阐述一下为什么使用滑动窗口可以去用来求解这类问题。对于这个题目如果我们使用暴力破解的方式大概应该怎么做?
以上图为例我们可以采取如下的解法 以一号位A为子串的终点向前探索一个最大不重复子串 以二号位D为子串的终点向前探索一个最大不重复子串 以三号位O为子串的终点向前探索一个最大不重复子串 … 我们可以借用map来统计字符字串是否有相同的元素这样我们大概可以得出以下解法
func search(s string, index int) int {m : make(map[uint8]int)res : 0for i : index; i 0; i-- {if _, ok : m[s[i]]; ok {break}m[s[i]] 1res}return res
}func lengthOfLongestSubstring(s string) int {res : 0for i : 0; i len(s); i {res max(res, search(s, i))}return res
}func max(a, b int) int {if a b {return a} else {return b}
}这种解法的算法复杂度是o(n2)读者可以注意到其实这个解法中做了很多重复性质的工作。我们在每一次切换字符串终点的时候都在重新往前推进逐个统计当前字符子串中是否有相同元素。但其实历史元素中的最大不重复字符子串是已经统计过的。如下图所示我们以A为字符串末尾时前面一个元素作为字符串末尾的最长不重复字串我们时已经计算过的。
以B为末端最长子串AODB
使用map统计的结是:
A:1
O:1
D:1
B:1我们在右端新增一个元素A会发现统计map变成了
以A为末端最长子串AODBA
使用map统计的结是:
A:2
O:1
D:1
B:1为了保证子字符串不含相同元素我们要将左端收缩到删除重复元素A。 这么一同分析题解就简化成了一个滑动窗口的解法。滑动窗口的右端不断增加元素如果滑动窗口有相同元素就收缩左端。这种解法的时间复杂度简化到了o(n)。
