温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

leetcode中如何查看无重复字符的最长子串

发布时间:2022-01-17 11:46:55 来源:亿速云 阅读:121 作者:小新 栏目:大数据

这篇文章主要介绍了leetcode中如何查看无重复字符的最长子串,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。

 

题目链接

https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

 

题目描述

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: "abcabcbb"输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
 

示例 2:

输入: "bbbbb"输出: 1解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
 

示例 3:

输入: "pwwkew"输出: 3解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。     请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
 
 

解题方案

 

思路

  • 标签:滑动窗口

  • 暴力解法时间复杂度较高,会达到O(n^2),故而采取滑动窗口的方法降低时间复杂度

  • 定义一个map数据结构存储(k,v),其中key值为字符,value值为字符位置+1,加1表示从字符位置后一个才开始不重复

  • 我们定义不重复子串的开始位置为start,结束位置为end

  • 随着end不断遍历向后,会遇到与[start, end]区间内字符相同的情况,此时将字符作为key值,获取其value值,并更新start,此时[start, end]区间内不存在重复字符

  • 无论是否更新start,都会更新其map数据结构和结果ans。

  • 时间复杂度:O(n)

 

代码

class Solution {    public int lengthOfLongestSubstring(String s) {        int n = s.length(), ans = 0;        Map<Character, Integer> map = new HashMap<>();        for (int end = 0, start = 0; end < n; end++) {            char alpha = s.charAt(end);            if (map.containsKey(alpha)) {                start = Math.max(map.get(alpha), start);            }            ans = Math.max(ans, end - start + 1);            map.put(s.charAt(end), end + 1);        }        return ans;    }}
 
 

画解

leetcode中如何查看无重复字符的最长子串

leetcode中如何查看无重复字符的最长子串

leetcode中如何查看无重复字符的最长子串

leetcode中如何查看无重复字符的最长子串

leetcode中如何查看无重复字符的最长子串

leetcode中如何查看无重复字符的最长子串

leetcode中如何查看无重复字符的最长子串


感谢你能够认真阅读完这篇文章,希望小编分享的“leetcode中如何查看无重复字符的最长子串”这篇文章对大家有帮助,同时也希望大家多多支持亿速云,关注亿速云行业资讯频道,更多相关知识等着你来学习!

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI