题目
Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
给出一个字符串,求出最长的无重复字符的子串的长度。
解题思路
滑动窗口:
- 移动窗口的右边界
right
, - 在
map
中寻找right
所指字符chare
- 找到则说明为重复字符,取
map[chare] + 1
和left
较大值,更新窗口左边界left
- 没找到则将
chare
和索引right
加入到map
中
- 找到则说明为重复字符,取
- 取
right - left + 1
和res
较大值,更新结果res
代码实现
Runtime: 36 ms
Memory: 21.6 MB
func lengthOfLongestSubstring(_ s: String) -> Int {
//字符串长度小于 2 时,直接返回字符串长度
let sCount = s.count
if(sCount < 2){
return sCount
}
var res = 0,left = 0
var sArr = Array(s)
var map = [Character:Int]()
//遍历字符串
for right in 0 ..< sCount{
//获取 right 所指字符 chare
let chare = sArr[right]
//若 map 中含有 chare,则更新 left
if let rIdx = map[chare] {
left = max(left, rIdx + 1)
}
//将 chare 和 right 加入到 map 中
map[chare] = right
//更新 res
res = max(right - left + 1, res)
}
return res
}
网友评论