Loading [MathJax]/jax/input/TeX/config.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
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 删除。

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

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
Leetcode3——Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.
Tyan
2019/05/25
3350
LeetCode Problem 3: Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.
剑影啸清寒
2019/05/26
3820
【LeetCode题解---003】Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.
周三不加班
2019/09/04
4450
【LeetCode题解---003】Longest Substring Without Repeating Characters
3. Longest Substring Without Repeating Characters(HashSet + 双指针)
Given a string, find the length of the longest substring without repeating characters.
yesr
2019/03/14
3330
Leetcode 3. Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.
xindoo
2021/01/21
3910
LeetCode 3. Longest Substring Without Repeating Characters题目分析
样例 例如,在"abcabcbb"中,其无重复字符的最长子字符串是"abc",其长度为 3。
desperate633
2018/08/22
3450
Sliding Window - 3. Longest Substring Without Repeating Characters
3. Longest Substring Without Repeating Characters
ppxai
2020/09/23
3150
LeetCode - Longest Substring Without Repeating Characters
最近启动了刷 LeetCode 的进程,Accepted 了几道题,但两天不到就忘了,即使是留了注释,想想写写笔记还是蛮有必要的,但我不希望不经思考整理就贴一堆代码,把博客搞的乱糟糟的,像 XSDN、XX园、X书 一样,所以也只是想把一些印象深刻的部分,留个笔记。
zgq354
2019/11/24
4710
LeetCode——Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1.
全栈程序员站长
2022/01/04
1780
LeetCode之Longest Substring Without Repeating Characters
这次的题目是找出字符串中最长不重复子串,一开始还以为跟最长匹配子串类似,需要用到动态规划呢,结果还是自己想太多了,偷看了一眼Tag,才发现只需要用hashmap和两个指针就能搞定。 算法的主要思想是:初始化两个指针head和tail,分别指向字符串初始位置0,并初始化一个hashmap,key为考察中的字符,value为对应字符所在位置。然后一个while循环,直至tail到达字符串尾部,在循环的每一步,首先会检查s[tail]是否存在于hashmap中,如果没有,则插入,否则找出s[tail]之前出现过的
forrestlin
2018/05/24
4790
003. 无重复字符的最长子串 | Leetcode题解
题目要求连续, 我们考虑使用滑动窗口。而这道题就是窗口大小不固定的滑动窗口题目,然后让我们求满足条件的窗口大小的最大值,这是一种非常常见的滑动窗口题目。
苏南
2020/12/16
5780
003. 无重复字符的最长子串 | Leetcode题解
Sliding Window - 395. Longest Substring with At Least K Repeating Characters
395. Longest Substring with At Least K Repeating Characters
ppxai
2020/09/23
4810
3. Longest Substring Without Repeating Characters(无重复字符的最长子串)
Given a string, find the length of the longest substring without repeating characters.
砖业洋__
2023/05/06
1480
3. Longest Substring Without Repeating Characters(无重复字符的最长子串)
LeetCode——Longest Substring Without Repeating Characters
题目: Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the lengt
felixzhao
2018/03/16
6520
无重复字符的最长子串
空间复杂度为O(∣Σ∣),其中 Σ 表示字符集(即字符串中可以出现的字符),∣Σ∣ 表示字符集的大小。
你好戴先生
2020/09/03
7830
【LeetCode题解-005】Longest Palindrome Substring
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
周三不加班
2019/09/04
4780
【LeetCode题解-005】Longest Palindrome Substring
LeetCode: 3_Longest Substring Without Repeating Characters | 求没有重复字符的最长子串的长度 | Medium
题目: Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the lengt
Linux云计算网络
2018/01/11
4750
搞定大厂算法面试之leetcode精讲20.字符串
方法1.截取字符串,循环字符串,遇到#就截掉最后一个字符,循环完毕之后,最后比较两个去除掉#退格之后的字符串是否相等,时间复杂度O(m+n),m、n是两个字符串的长度。空间复杂度O(1)
全栈潇晨
2021/12/04
7360
【Leet Code】3. Longest Substring Without Repeating Characters
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
韩旭051
2019/11/08
2890
395. Longest Substring with At Least K Repeating Characters
这是一个经典的分治法解决的问题,关键在于我们如何将这个问题分解为更小的子问题。反过来想,这个子字符串一定不包含什么元素呢?当一个元素出现的总次数小于k,那么该元素一定不在子字符串中,只需要将其作为分界点,分别找出左半部分和右半部分的满足条件的最长子字符串。
眯眯眼的猫头鹰
2019/03/13
4430
推荐阅读
相关推荐
Leetcode3——Longest Substring Without Repeating Characters
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档