LeetCode3.滑动窗口: 双指针法(Kotlin语言)-无重复字符的最长子串
LeetCode3.滑动窗口: 双指针法(Kotlin语言)-无重复字符的最长子串
LeetCode3.滑动窗口: 双指针法(Kotlin语言)-无重复字符的最长子串
题目描述
无重复字符的最长子串
- 给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。
示例 1:
输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
解题思路
暴力破解法
/**
* 暴力破解法: 遍历所有子串,会出现超时 LTE
*/
fun lengthOfLongestSubstring(s: String): Int {
var ans = 0
// 遍历所有子串
val charArray = s.toCharArray()
val n = charArray.size
if (n == 0) return 0
for (i in 0 until n) {
for (j in i..n) {
val substr = s.substring(i, j)
if (isUniqString(substr)) {
ans = Math.max(ans, substr.length)
}
}
}
return ans
}
/**
* 判断字符串中的字符是否全部无重复
*/
fun isUniqString(s: String): Boolean {
val charArray = s.toCharArray()
val len1 = charArray.size
val len2 = charArray.groupBy { it }.keys.size
return len1 == len2
}滑动窗口: 双指针法
滑动窗口是数组/字符串问题中常用的抽象概念。窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合，即 [i, j)（左闭，右开）。而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。例如，我们将 [i, j) 向右滑动 1 个元素，则它将变为 [i+1, j+1) (左闭，右开）。
使用 HashSet 作为滑动窗口，我们可以用 O(1) 的时间来完成对字符是否在当前的子字符串中的检查。
回到我们的问题，我们使用 HashSet 将字符存储在当前窗口 [i, j)（最初 j = i）中。 然后我们向右侧滑动索引 j，如果它不在 HashSet 中，我们会继续滑动 j。直到 s[j] 已经存在于 HashSet 中。
此时，我们找到的没有重复字符的最长子字符串将会以索引 i 开头。 如果我们对所有的 i 这样做，就可以得到答案。
滑动窗口-双指针法源代码
class Solution {
fun lengthOfLongestSubstring(s: String): Int {
var ans = 0
var left = 0
var right = 0
val n = s.length
val window = mutableSetOf<Char>()
while (left < n && right < n) {
// slide right pointer
if (!window.contains(s[right])) {
window.add(s[right++])
ans = Math.max(ans, right - left)
} else {
// slide left pointer
window.remove(s[left++])
}
}
return ans
}
}3. Longest Substring Without Repeating Characters
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.
参考资料
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters