LeetCode3. Longest Substring Without Repeating Characters

题目

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given “abcabcbb”, the answer is “abc”, which the length is 3.

Given “bbbbb”, the answer is “b”, with the length of 1.

Given “pwwkew”, the answer is “wke”, with the length of 3. Note that the answer must be a substring, “pwke” is a subsequence and not a substring.

找出一个字符串的不含有重复字符的最长子串,注意,子串需要连续而子序列不需要。

解题思路

这题的思路很明显是动态规划,O(n^2)的方法很容易想到,即用一个bool类型的二维数组表示一个子串是否是非重复子串,然后一路递推就可以,但这明显不是我们想要的。 可不可以一次便利得出结果?可以

public int lengthOfLongestSubstring(String s) {
        //指向正在遍历的字母的指针
        int start = 0;
        int end = -1;
        //指向最长的子串的开头结尾的指针
        int resStart = 0;
        int resEnd = -1;
        //指向上一个子串的指针
        int tmpStart = 0;
        int tmpEnd = -1;
        //用来存储不重复的字符,值表示字符所在位置
        HashMap<Character, Integer> set = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            //如果发现字符重复,进行一系列操作
            if (set.containsKey(s.charAt(i))) {
                //先保留这个子串,方便map删除
                tmpStart = start;
                tmpEnd = end;
                //如果正在遍历的子串长度大于之前的最大值,就替换
                if (end - start + 1 >= resEnd - resStart + 1) {
                    resStart = start;
                    resEnd = end;
                }
                //重新设置开始值为重复的字符的下一位
                start = set.get(s.charAt(i)) + 1;
                end = i;

                //如果与前一位相同,直接清空map
                if (s.charAt(i) == s.charAt(i - 1))
                    set.clear();
                else {
                    //否则仅清空相同位之前的字符
                    int index = set.get(s.charAt(i));
                    for (int k = tmpStart; k <= index; k++) {
                        set.remove(s.charAt(k));
                    }
                }
            } else {
                //不重复,直接向后遍历
                end++;
            }
            //把不重复的字符加入map
            set.put(s.charAt(i), i);
        }
        //因为存在最后一位字符所在的子串刚好是最长的可能,而这时又不会触发上方的语句,所以需要在结尾加个判断
        return resEnd - resStart + 1 > end - start + 1 ? resEnd - resStart + 1 : end - start + 1;
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏北京马哥教育

看完这篇文章还不懂Python中的闭包,请拍死小编

1664
来自专栏MyBlog

Effective.Java 读书笔记(11)关于clone方法

说到clone方法,我们来提一提Cloneable这个接口,这个接口是用来作为一种标记某对象允许被clone的一种混合接口,可是不幸运的是,这个接口并没能起到该...

972
来自专栏Java编程

四道Java基础题,你能对几道?

如果这道题你能得出正确答案,并能了解其中的原理的话。说明你基础还可以。如果你的答案 是 true 和true的话,你的基础就有所欠缺了。

1K1
来自专栏C/C++基础

C++中函数重载、隐藏、覆盖和重写的区别

C++规定在同一作用域中,同名函数的形式参数(指参数的个数、类型或者顺序)不同时,构成函数重载。

982
来自专栏算法修养

温故KMP算法

最近由于某些原因,又回顾了一次KMP算法。上一次回顾KMP算法还是在刷题的时候遇到的: http://blog.csdn.net/dacc123/article...

3568
来自专栏java一日一条

如何读懂并写出装逼的函数式代码

今天在微博上看到了 有人分享了下面的这段函数式代码,我把代码贴到下面,不过我对原来的代码略有改动,对于函数式的版本,咋一看,的确令人非常费解,仔细看一下,你可能...

542
来自专栏工科狗和生物喵

【计算机本科补全计划】《C++ Primer》:表达式以及运算符

正文之前 好久没写了啊!!感觉自己都已经不爱简书了。不过其实我的《C++ Primer》已经看到400多页了。然而网络笔记还停留在120页,这个很骚啊,意味着我...

3437
来自专栏云霄雨霁

Java--集合类之Vector、BitSet、Stack、Hashtable

1617
来自专栏小狼的世界

PHP中正则的使用

正则表达式,作为一种快速、便捷的处理字符串的工具,在各种编程语言中都有着广泛的用途,通过在PHP中的一些使用,下面记录一下关于PHP中正则使用的一些技巧。

913
来自专栏LeetCode

LeetCode <BT> 200. Number of Islands

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands...

430

扫码关注云+社区