LeetCode 第三题: 无重复字符的最长子串

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

题目描述

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

示例

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

解题思路 - 滑动窗口法

  这个问题可以用“滑动窗口”技术来解决。滑动窗口是数组/字符串问题中常用的抽象概念。窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合,即 [i, j)(左闭右开)。在这里,我们将使用哈希集合来检查一个字符是否已经在当前的子串中。我们可以使用两个指针表示字符串中的某个子串(或窗口)的左右边界。右指针向右移动扩大窗口直到右指针到达字符串尽头;左指针向右移动以减小窗口直到窗口不再包含重复字符。在移动指针的过程中,我们记录并更新不含重复字符的最长子串的长度。

Go语言实现 - 滑动窗口法

func lengthOfLongestSubstring(s string) int {
   
    charIndexMap := make(map[byte]int)
    maxLength := 0
    for i, j := 0, 0; j < len(s); j++ {
   
        if index, ok := charIndexMap[s[j]]; ok {
   
            i = max(i, index)
        }
        maxLength = max(maxLength, j-i+1)
        charIndexMap[s[j]] = j + 1
    }
    return maxLength
}

func max(a, b int) int {
   
    if a > b {
   
        return a
    }
    return b
}

算法分析

  • 时间复杂度: O(n),其中 n 是字符串的长度。我们只需要遍历一次字符串即可。
  • 空间复杂度: O(min(m, n)),其中 m 是字符集的大小。这是因为哈希集合的大小取决于字符串中不同字符的数量,这个数量最大不会超过字符集的大小,同时也不会超过字符串的长度。

解题思路 - 优化的滑动窗口法

  虽然上述滑动窗口法已经很高效,但在某些情况下,当窗口内的字符被移除时,我们可以跳过窗口中的一些字符,直接移动到重复字符的下一个位置,这可以通过存储字符的最新索引来实现。

Go语言实现 - 优化的滑动窗口法

  这个方法与上面提到的滑动窗口法实际上是一样的。优化点主要在于如何更有效地更新左指针的位置。在实践中,由于这种情况出现的不多,所以实际的性能提升可能不大。因此,上面的实现已经足够满足大多数情况下的需求。

  ‍

相关文章
|
12天前
|
存储 算法 程序员
【Leetcode 程序员面试金典 01.01】判定字符是否唯一 —— 位运算|哈希表
可以使用哈希表或位运算来解决此问题:由题可知s[i]仅包含小写字母,int[26]即能表示字符的出现次数;
|
12天前
|
算法
LeetCode算法题---无重复字符的最长子串、寻找两个正序数组的中位数(三)
LeetCode算法题---无重复字符的最长子串、寻找两个正序数组的中位数(三)
41 0
|
12天前
|
网络协议
《 LeetCode 热题 HOT 100》——无重复字符的最长子串
《 LeetCode 热题 HOT 100》——无重复字符的最长子串
|
12天前
【Leetcode 2707】字符串中的额外字符 —— 动态规划
1. 状态定义:把`s[i−1]`当做是额外字符,`d[i] = d[i−1] + 1` 2. 状态转移方程:遍历所有的`j(j∈[0,i−1])`,如果子字符串`s[j...i−1]`存在于`dictionary`中,那么`d[i] = min d[j] 3. 初始状态`d[0] = 0`,最终答案为`d[n]`
|
12天前
leetcode:3. 无重复字符的最长子串
leetcode:3. 无重复字符的最长子串
18 0
|
12天前
|
算法
leetcode:387. 字符串中的第一个唯一字符
leetcode:387. 字符串中的第一个唯一字符
15 0
|
12天前
|
存储 索引
力扣1445 连续字符
力扣1445 连续字符
23 0
|
2天前
|
算法 索引
力扣刷题【第一期】
这是一个关于算法的总结,包含7个不同的问题。1)爬楼梯问题,使用动态规划,通过迭代找到到达n阶楼梯的不同方法数。2)两数之和,通过双重循环找出数组中和为目标值的两个数的索引。3)移动零,使用双指针将数组中的0移到末尾。4)合并有序链表,创建新链表按升序合并两个链表。5)删除链表重复值,遍历链表删除重复元素。6)环形链表检测,使用快慢指针判断链表是否有环。7)相交链表,计算链表长度找
7 1
|
2天前
|
存储 Java
JAVA数据结构刷题 -- 力扣二叉树
JAVA数据结构刷题 -- 力扣二叉树
9 0