Fork me on GitHub

3. 无重复字符的最长子串

0 - 算法, 0.1 - 算法题目, 0.1.1 - 中等 本文总阅读量次

题目

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

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

示例 2:

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

示例 3:

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

提示：

  • 0 <= s.length <= 5 * 10^4
  • s 由英文字母、数字、符号和空格组成

简介

1
2
3
4
5
巧妙的使用 HashMap<Char, Int> 记录每个字符的最新的位置
巧妙的确定了每个元素对应的滑动窗口的左边界
关键词：
HashMap <Char, Int>用以查找位置
窗口长度不固定，遍历指针作为左边界

正文

本题的巧妙在于使用 HashMap 和 遍历指针构建了一个滑动窗口

在寻找滑动窗口的时候，我们总是固定住一端位置去寻找另一端的位置，通常需要我们找到两个端点之间的关系

来分析滑动窗口的性质：左边届位置，右边界的位置，滑动窗口的长度
三者有以下这些关系：滑动窗口的长度 = 滑动窗口右边届 - 滑动窗口左边界
无论算法如何变化，我们知二求一

我们分析，遍历指针和左右边界的关系有三
情况一：遍历指针是滑动窗口的左边界
情况二：遍历指针是滑动窗口的右边界
情况三：遍历指针在滑动窗口的中间

结合滑动窗口的性质
情况一：知道窗口的长度，以遍历指针为左边界
情况二：窗口长度不固定，新增的元素决定窗口的长度，也就是左边界的位置
情况三：对于滑动窗口算法，通常情况下遍历指针要么位于窗口的左边界，要么位于右边界，用于控制窗口的扩展和收缩。在常规的滑动窗口算法中，遍历指针并不位于窗口的中间位置。

显然这种是情况二

当滑动窗口的位置和长度变化受制于新增的元素时，我们将遍历指针设置为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    fun lengthOfLongestSubstring(s: String): Int {
        var maxLen = 0 // 最长不含重复字符子串的长度
        var left = 0 // 窗口左边界
        val map = HashMap<Char, Int>() // 哈希表记录字符最后出现的位置

        for(right in s.indices){
            val char = s[right]

            if(map.containsKey(char) && map[char]!! >= left){
                left = (map[char]?: 0) + 1
            }

            map[char] = right
            maxLen = maxOf(maxLen, right - left + 1)
        }
        return maxLen
    }
}
0 - 算法, 0.1 - 算法题目, 0.1.1 - 中等