使用kotlin解决这个问题:3. 无重复字符的最长子串 给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。 示例 2: 输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。 示例 3: 输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。 请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。 提示: 0 <= s.length <= 5 * 104 s 由英文字母、数字、符号和空格组成
时间: 2024-02-13 11:00:31 浏览: 211
可以使用滑动窗口的方法来解决这个问题。滑动窗口是一种常用的数组/字符串的算法,用于解决子串或子数组的问题。
具体实现:
1. 定义一个哈希集合,用于存放当前窗口中的字符。
2. 初始化左指针和右指针为 0,最长子串长度为 0。
3. 当右指针小于字符串长度时,进行循环:
- 如果当前字符不在哈希集合中,将其加入哈希集合,右指针加一。
- 如果当前字符在哈希集合中,将左指针向右移动一位,同时将左指针所在字符从哈希集合中移除。
4. 更新最长子串长度为当前窗口大小和最长子串长度的较大值。
5. 返回最长子串长度。
下面是 Kotlin 代码实现:
```kotlin
fun lengthOfLongestSubstring(s: String): Int {
val set = hashSetOf<Char>()
var left = 0
var right = 0
var maxLen = 0
while (right < s.length) {
if (!set.contains(s[right])) {
set.add(s[right])
right++
maxLen = maxOf(maxLen, set.size)
} else {
set.remove(s[left])
left++
}
}
return maxLen
}
```
时间复杂度为 O(n),空间复杂度为 O(min(n, m)),其中 m 为字符集大小。
阅读全文
相关推荐












