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

Kotlin 开发者社区

国内第一Kotlin 开发者社区公众号,主要分享、交流 Kotlin 编程语言、Spring Boot、Android、React.js/Node.js、函数式编程、编程思想等相关主题。

越是喧嚣的世界,越需要宁静的思考。

相关文章阅读

动态规划算法图文详解(Kotlin语言):二维矩阵中找到只包含&nbsp;1&nbsp;的最大正方形(LeetCode-221)

Java并发多线程高频面试题

滑动窗口算法原理图解(Kotlin语言)长度最小的子数组-LeetCode209

图文详解布隆过滤器(Bloom Filter):如何快速判断某URL是否在20亿的网址URL集合中?

LRUCache的几种Java实现

【BAT面试题宝库附详尽答案解析】图解分布式一致性协议Paxos算法

Linux内核的 4 大 IO 调度算法

如何设计一个消息中间件?消息中间件的总体架构

[数据结构与算法]1.冒泡排序(Bubble Sort)

[数据结构与算法]2.快速排序Java实现

我来评几句
登录后评论

已发表评论数()

相关站点

热门文章