无重复字符的最长子串

关注顶级算法修炼内功

顶级算法后台回复 1024 有特别礼包

责编：顶级算法

上一篇精彩：这些书，真tm肝……

大家好，我是顶级算法。
排序序列：
1、程序员必知必会的排序一：冒泡排序2、程序员必知必会的排序二：快速排序3、程序员必知必会的排序三：直接插入排序4、程序员必知必会的排序四：希尔排序5、程序员必知必会的排序五：拓扑排序6、程序员必知必会的排序六：选择排序7、程序员必知必会的排序七：归并排序

• 定义一个map数据结构存储（k，v），其中key值为字符，value值为字符位置+1，加1表示从字符位置后一个才开始不重复。扩展：这些书，真tm肝……

• 我们定义不重复子串的开始位置为start，结束位置为end

• 随着end不断遍历向后，会遇到与【start，end】区间内字符相同的情况，此时将字符作为key值，获取其value值，并更新start，此时【start，end】区间内不存在重复字符。另外搜索公众号Linux就该这样学后台回复“git书籍”，获取一份惊喜礼包。

• 无论是否更新start，都会更新其map数据结构和结果ans。

• 时间复杂度：O（n）

代码：

 public int lengthOfLongestSubstring(String s) {
        int length=s.length();
        int max=0;
        //存放字符以及
        Map<Character,Integer> map =new HashMap<>();
        for (int start = 0,end=0; end <length ; end++) {
            char element=s.charAt(end);
            if (map.containsKey(element)){
                //为了防止连续重复字符，这里要进行一次判断
                //+1表示该元素后一个元素才是不重复字符串的开始
                start=Math.max(map.get(element)+1,start);
            }
            max=Math.max(max,end-start+1);
            //保存最后一个该结点的位置；
            map.put(element,end);
        }
        return max;
    }

觉得不错？欢迎转发分享给更多人

最近有一些小伙伴，让我帮忙找一些 面试题 资料，于是我翻遍了收藏的 10T 资料后，汇总整理出来，可以说是程序员面试必备！所有资料都整理到网盘了，欢迎下载！

👆扫码回复【面试题】即可获取👆

公众号后台回复 算法 或者 算法心得 有惊喜礼包！顶级算法交流群

 「顶级算法」建立了读者算法交流群，大家可以添加小编微信进行加群。欢迎有想法、乐于分享的朋友们一起交流学习。

扫描添加好友邀你进算法群，加我时注明【姓名+公司+职位】

版权申明：内容来源网络，版权归原作者所有。如有侵权烦请告知，我们会立即删除并表示歉意。谢谢。

往日分享：