首页 > 编程语言 > 详细

LeetCode之无重复字符的最长子串超详细java讲解

时间:2021-05-30 00:29:33      阅读:26      评论:0      收藏:0      [点我收藏+]

技术分享图片

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

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

思路一:利用滑动窗口:类似于一个队列,比如例题中的 abcav,进入这个窗口为 abc 满足题目要求,当再进入 a,队列变成了 abca,这时候不满足要求。所以,我们要移动这个队列,此时的窗口值为bca
即left移动到,b位置,移动到重复值a的后一位。相当于将与当前相同的值的左边全部移出窗口。

 


时间复杂度:O(n)

完整代码如下:
public int lengthOfLongestSubstring(String s){
        HashMap<Character,Integer> map = new HashMap<>();
        int max = 0;   //最长长度
        int left = 0;  //滑动窗口最初为零
        for(int i = 0;i<s.length();i++){
            if(map.containsKey(s.charAt(i))){      //如果包含,则更新left,
                left = Math.max(left,map.get(s.charAt(i)+1)); //之所以要不能直接取map.get(s.charAt(i))+1是因为当前值可能不包含在有效字段里面
            }
            map.put(s.charAt(i),i);//更新left后,不管原来的 s.charAt(i) 是否在最长子段中,我们都要将 s.charAt(i) 的位置更新为当前的i,
            //如果包含了,则会把之前的给覆盖掉。
            max = Math.max(max,i-left+1);  //更新max
        }
        return max;
    }

 

技术分享图片

 

 

 2021-05-29

 

 

 



LeetCode之无重复字符的最长子串超详细java讲解

原文:https://www.cnblogs.com/liuhuaabcp/p/14826586.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!