「LeetCode」剑指Offer-48最长不含重复字符的子字符串

简介: 「LeetCode」剑指Offer-48最长不含重复字符的子字符串

image.png

前言🌧️



算法,对前端人来说陌生又熟悉,很多时候我们都不会像后端工程师一样重视这项能力。但事实上,算法对每一个程序员来说,都有着不可撼动的地位。


因为开发的过程就是把实际问题转换成计算机可识别的指令,也就是《数据结构》里说的,「设计出数据结构,在施加以算法就行了」。


当然,学习也是有侧重点的,作为前端我们不需要像后端开发一样对算法全盘掌握,有些比较偏、不实用的类型和解法,只要稍做了解即可。


题目🦀


剑指 Offer 48. 最长不含重复字符的子字符串


难度中等


请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。


示例 1:


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


示例 2:


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


示例 3:


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

提示:


  • s.length <= 40000


解题思路🌵



  • 此题可以采用动态规划来解决,可以将问题拆分为很多叠加的子问题求合
  • 也可以采用双指针,滑动窗口来解决


解法1🔥


var lengthOfLongestSubstring = function(s) {
    let tem=0;
    let repeatIndex=0;
    const dp=[1]
    const map=new Map()
    for(let i=0;i<s.length;i++){
        if(!map.has(s[i])){
            if(i==0){
            dp[i]=1
            }else{
            dp[i]=dp[i-1]+1
            }
        }else{
            //这一步很关键,如果以前出现的字符位置大于了前一个dp[i-1]的值,表示前一个数xxx到当前数xxx中间肯定存在重复
            if((i-map.get(s[i]))>dp[i-1]){
                dp[i]=dp[i-1]+1
            }else{
            dp[i]=i-map.get(s[i])
            }
        }
        map.set(s[i],i)
        tem=dp[i]>tem?dp[i]:tem
    }
    return tem
};

时间复杂度:O(n)


空间复杂度:O(1)


解法2🔥


//滑动窗口
var lengthOfLongestSubstring = function(s) {
    let window=[]
    let max=0
    for(let i=0;i<s.length;i++){
        if(!window.includes(s[i])){
            window.push(s[i])
        }else{
            window=window.slice(window.indexOf(s[i])+1)
            window.push(s[i])
        }
      max=max<window.length?window.length:max
    }
    return max
};

时间复杂度:O(n)


空间复杂度:O(1)


结束语🌞


image.png


那么鱼鱼的LeetCode算法篇的剑指Offer-48最长不含重复字符的子字符串⚡️就结束了,算法这个东西没有捷径,只能多写多练,多总结,文章的目的其实很简单,就是督促自己去完成算法练习并总结和输出,菜不菜不重要,但是热爱🔥,喜欢大家能够喜欢我的短文,也希望通过文章认识更多志同道合的朋友,如果你也喜欢折腾,欢迎加我好友,一起沙雕,一起进步


相关文章
|
2天前
|
存储 算法 数据挖掘
深入解析力扣166题:分数到小数(模拟长除法与字符串操作详解及模拟面试问答)
深入解析力扣166题:分数到小数(模拟长除法与字符串操作详解及模拟面试问答)
|
2天前
|
存储 算法 数据可视化
深入解析力扣161题:相隔为 1 的编辑距离(逐字符比较与动态规划详解)
深入解析力扣161题:相隔为 1 的编辑距离(逐字符比较与动态规划详解)
|
2天前
|
存储 算法 数据可视化
深入解析力扣157题:用Read4高效读取N个字符(多种解法与详细图解)
深入解析力扣157题:用Read4高效读取N个字符(多种解法与详细图解)
|
2天前
|
存储 算法 数据可视化
深入解析力扣159题:至多包含两个不同字符的最长子串(滑动窗口法详细图解)
深入解析力扣159题:至多包含两个不同字符的最长子串(滑动窗口法详细图解)
|
3天前
|
存储 算法 数据可视化
LeetCode 题目 97:动态规划、递归到广度优先搜索BFS 实现交错字符串
LeetCode 题目 97:动态规划、递归到广度优先搜索BFS 实现交错字符串
|
3天前
|
存储 SQL 算法
LeetCode 题目 87:递归\动态规划\哈希实现 扰乱字符串
LeetCode 题目 87:递归\动态规划\哈希实现 扰乱字符串
|
3天前
|
存储 算法 数据挖掘
LeetCode 题目 43:字符串相乘 多种算法分析对比 【python】
LeetCode 题目 43:字符串相乘 多种算法分析对比 【python】
|
17天前
|
索引
【力扣刷题】两数求和、移动零、相交链表、反转链表
【力扣刷题】两数求和、移动零、相交链表、反转链表
21 2
【力扣刷题】两数求和、移动零、相交链表、反转链表
|
5天前
|
存储 算法
力扣链表刷题总结(简单)
力扣链表刷题总结(简单)
|
16天前
|
算法
"刷题记录:哈希表+双指针 | leetcode-2465. 不同的平均值数目 "
该文段是一篇关于编程题目的解答,主要讨论如何找到数组中所有不同平均值的个数。作者首先使用排序和哈希集来解决,将数组转为列表排序后,通过双指针计算平均值并存入哈希集以去重。然后,作者发现可以优化方案,通过双指针在排序后的数组中直接计算两数之和,用哈希集记录不重复的和,从而避免实际计算平均值,提高了算法效率。最终代码展示了这两种方法。
21 0