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 条评论
登录 后参与评论

相关文章

来自专栏技术专栏

Python3入门与实践(一): 基本类型整理

1053
来自专栏数据结构与算法

19:字符串移位包含问题

19:字符串移位包含问题 总时间限制: 1000ms 内存限制: 65536kB描述 对于一个字符串来说,定义一次循环移位操作为:将字符串的第一个字符移动到...

4438
来自专栏开源优测

[快学Python3]二分查找[策略优化版本]

概述 在上文《二分查找》中,我们了解了二分查找基本实现原理和具体的实现算法。 但大家有没有发现,如果目标查找值,如果在查找序列中存在多个,则查找返回的索引值,会...

3095
来自专栏游戏杂谈

LuaJit转义的问题

之前在项目中,处理类似!30转为表现的字符串时,有人写了这样的一段代码“\![1-2][0-9]”,当换成luajit时启动报错了,出错原因在于转义字符使用不对...

122
来自专栏数据结构与算法

P3373 【模板】线段树 2 区间求和 区间乘 区间加

题目描述 如题,已知一个数列,你需要进行下面两种操作: 1.将某区间每一个数加上x 2.将某区间每一个数乘上x 3.求出某区间每一个数的和 输入输出格式 输...

34811
来自专栏Python小屋

Python运算符含义汇总

本文以Python 3.5及其以后的版本为主进行介绍。 运算符功能说明+算术加法,列表、元组、字符串合并与连接-算术减法,集合差集*乘法,序列重复/真除法//求...

2797
来自专栏Jackson0714

正则表达式全部符号解释

33815
来自专栏Python

Python中的栈溢出及解决办法

1.递归函数 在函数内部,可以调用其他函数。如果一个函数在内部调用自身本身,这个函数就是递归函数。 举个例子,我们来计算阶乘n! = 1 x 2 x 3 x ....

2744
来自专栏Jackson0714

正则表达式全部符号解释

976
来自专栏书山有路勤为径

逆序数

LeetCode 315. Count of Smaller Numbers After Self

451

扫码关注云+社区