LeetCode - 无重复字符的最长子串(滑动窗口解法)

Q:给定一个字符串,找出其中不含有重复字符的 最长子串 的长度。

输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

A:这个题目用暴力循环可以轻松解决,但是其时间复杂度会很高:O(n^3),可以用滑动窗口来解决该问题:

滑动窗口:其实就是一个队列,比如题中的 abcabcbb,进入这个队列(窗口)为 abc 满足题目要求,当再进入 a,队列变成了 abca,这时候不满足要求。所以,要移动这个队列。只要把队列的左边的元素移出就行了,直到满足题目要求,一直维持这样的队列,找出队列出现最长的长度时候,求出解。

fun lengthOfLongestSubstring(s: String): Int {
if (s.length == 0 )return 0
val map = HashMap<Char,Int>()
var max = 0
var left = 0

for (i in 0..s.length-1){
if (map.containsKey(s.get(i))){
left = Math.max(left,map.get(s.get(i))!!+1)
}
map.put(s.get(i),i)
max = Math.max(max,i-left+1)
}
return max
}
点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像

Title - Artist
0:00