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

相关文章

来自专栏码匠的流水账

java9系列(五)Stack-Walking API

java9新增这个类的目的是提供一个标准API用于访问当前线程栈,之前只有Throwable::getStackTrace、Thread::getStackTr...

421
来自专栏我和未来有约会

简练的视图模型 ViewModel

patterns & practices Developer Center 发布了 Unity Application Block 1.2 for Silver...

2179
来自专栏WOLFRAM

向日葵中的数学之美

1833
来自专栏前端儿

Web 前端颜色值--字体--使用,整理整理

颜色值 CSS 颜色使用组合了红绿蓝颜色值 (RGB) 的十六进制 (hex) 表示法进行定义。对光源进行设置的最低值可以是 0(十六进制 00)。最高值是 2...

2302
来自专栏专知

2018年SCI期刊最新影响因子排行,最高244,人工智能TPAMI9.455

2018年6月26日,最新的SCI影响因子正式发布,涵盖1万2千篇期刊。CA-Cancer J Clin 依然拔得头筹,其影响因子今年再创新高,达244.585...

1282
来自专栏MelonTeam专栏

Bitmap 源码阅读笔记

导语: Android 系统上的图片的处理,跟Bitmap 这个类脱不了关系,我们有必要去深入阅读里面的源码,以便在工作中能更好的处理Bitmap相关的问题...

2498
来自专栏Golang语言社区

Knapsack problem algorithms for my real-life carry-on knapsack

I'm a nomad and live out of one carry-on bag. This means that the total weight o...

1142
来自专栏余生开发

echarts太阳分布图-饼图来回穿梭

var dom = document.getElementById("container");

1182
来自专栏码匠的流水账

聊聊HystrixThreadPool

hystrix-core-1.5.12-sources.jar!/com/netflix/hystrix/HystrixThreadPool.java

781
来自专栏linux驱动个人学习

高通Audio中ASOC的machine驱动

ASoC被分为Machine、Platform和Codec三大部分,其中的Machine驱动负责Platform和Codec之间的耦合以及部分和设备或板子特定的...

9774

扫码关注云+社区