首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >LeetCode3. Longest Substring Without Repeating Characters

LeetCode3. Longest Substring Without Repeating Characters

作者头像
用户1665735
发布于 2018-06-20 08:54:35
发布于 2018-06-20 08:54:35
54100
代码可运行
举报
文章被收录于专栏:kevindroidkevindroid
运行总次数:0
代码可运行

题目

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类型的二维数组表示一个子串是否是非重复子串,然后一路递推就可以,但这明显不是我们想要的。 可不可以一次便利得出结果?可以

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
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;
    }
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2017年11月28日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
CA1024:在适用处使用属性
在大多数情况下,属性表示数据,方法执行操作。 访问属性的方式类似于访问字段,这使得它们更易于使用。 如果一个方法具备以下条件之一,则该方法可能很适合成为属性:
用户4268038
2022/01/10
5340
CA1715:标识符应具有正确的前缀
接口名称应以大写的“I”开头,后跟另一个大写字母。 此规则报告与接口名称(如“MyInterface”和“IsolatedInterface”)相关的冲突。
呆呆
2022/02/19
5900
CA1012:抽象类型不应具有公共构造函数
抽象类型的构造函数只能由派生类型调用。 由于公共构造函数可创建类型的实例,但无法创建抽象类型的实例,因此具有公共构造函数的抽象类型在设计上是错误的。
用户4268038
2022/01/10
6070
CA1056:URI 属性不应是字符串
类型声明名称包含“uri”、“Uri”、“urn”、“Urn”、“url”或“Url”的字符串属性。
呆呆
2022/02/22
5760
CA1054:URI 参数不应为字符串
类型声明一个方法,该方法具有名称中包含“uri”、“Uri”、“urn”、“Urn”、“url”或“Url”的字符串参数,且类型未声明采用 System.Uri 参数的相应重载。
呆呆
2022/01/10
6430
CA1055:URI 返回值不应是字符串
方法名称包含“uri”、“Uri”、“urn”、“Urn”、“url”或“Url”,且方法返回一个字符串。
呆呆
2022/01/10
5930
CA1802:在合适的位置使用文本
某个字段被声明为 static 和 readonly(在 Visual Basic 中为 Shared 和 ReadOnly),并使用可在编译时计算的值初始化。
呆呆
2022/02/19
8670
CA1721:属性名不应与 get 方法冲突
成员的名称以“Get”开头,且其余部分与属性的名称匹配。 例如,包含名为“GetColor”的方法和名为“Color”的属性的类型将导致规则冲突。
呆呆
2022/02/19
4400
CA1819:属性不应返回数组
即使属性是只读的,该属性返回的数组也不受写入保护。 若要使数组不会被更改,属性必须返回数组的副本。 通常,用户不能理解调用这种属性的负面性能影响。 具体来说,他们可能将索引属性作为属性使用。
呆呆
2022/02/19
1.1K0
CA1060:将 P/Invoke 移动到 NativeMethods 类
方法使用平台调用服务访问非托管代码,不是 NativeMethods 类之一的成员。
呆呆
2022/01/10
7370
CA1003:使用泛型事件处理程序实例
某个类型包含的委托返回 void,且该委托的签名包含两个参数(第一个参数是对象,第二个参数是可以分配给 EventArgs 的类型),而且包含程序集面向的是 .NET。
用户4268038
2022/01/09
6110
CA1021:避免使用 out 参数
按引用(使用 out 或 ref)传递类型要求具有使用指针的经验,了解值类型和引用类型的不同之处,以及能处理具有多个返回值的方法。 另外,out 和 ref 参数之间的区别并未得到广泛了解。
用户4268038
2022/01/10
5740
CA1045:不要通过引用来传递类型
公共类型中的公共或受保护方法有一个 ref 参数,该参数采用基元类型、引用类型或不属于内置类型的值类型。
呆呆
2022/01/10
5750
CA1019:定义特性参数的访问器
特性可以定义强制自变量,在对目标应用该特性时必须指定这些自变量。 这些实参也称为位置实参,因为它们将作为位置形参提供给特性构造函数。 对于每一个强制变量,特性还必须提供一个相应的只读属性,以便可以在执行时检索该变量的值。 此规则检查是否已为每个构造函数参数定义了相应属性。
用户4268038
2022/01/10
5170
CA1018:用 AttributeUsageAttribute 标记特性
自定义特性上不存在 System.AttributeUsageAttribute 特性。
用户4268038
2022/01/10
2090
【愚公系列】2023年02月 .NET/C#知识点-委托、匿名方法、Lambda、泛型委托、表达式树的进化史
在 .NET 中,委托是一种类型,它可以持有对一个或多个方法的引用,并允许将这些方法作为参数传递给其他方法。.NET 中的委托类似于 C 和 C++ 中的函数指针,但具有更高的类型安全性和其他功能。
愚公搬代码
2023/02/16
8120
CA1050:在命名空间中声明类型
应在命名空间内声明类型以避免名称冲突,并作为一种在对象层次结构中组织相关类型的方式。 任何命名的命名称空间之外的类型均位于无法在代码中引用的全局命名空间中。
呆呆
2022/01/10
5710
CA1062:验证公共方法的参数
外部可见方法取消引用其中一个引用参数,而不验证该参数是否 null(Visual Basic 中 Nothing)。
呆呆
2022/01/10
8620
CA1044:属性不应是只写的
Get 访问器提供对属性的读取访问权限,而 set 访问器提供写入访问权限。 虽然可以接受且经常需要使用只读属性,但设计准则禁止使用只写属性。 这是因为允许用户设置值但又禁止该用户查看这个值不能提供任何安全性。 而且,如果没有读访问,将无法查看共享对象的状态,使其用处受到限制。
呆呆
2022/01/10
2380
CA1820:使用字符串长度测试是否有空字符串
使用 String.Length 属性或 String.IsNullOrEmpty 方法比较字符串比使用 Equals 更快。 这是因为 Equals 执行的 MSIL 指令比 IsNullOrEmpty 或执行以用于检索 Length 属性值并将其与零进行比较的指令数要多得多。
呆呆
2022/02/19
3670
相关推荐
CA1024:在适用处使用属性
更多 >
交个朋友
加入[后端] 腾讯云技术交流站
后端架构设计 高可用系统实现
加入腾讯云技术交流站
前端技术前沿探索 云开发实战案例分享
加入架构与运维工作实战群
高并发系统设计 运维自动化实践
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档