力扣题目-无重复字符的最长子串(C++,python,java)

简介: 力扣题目-无重复字符的最长子串(C++,python,java)

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


示例 :


输入: “abcabcbb”

输出: 3

解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。


C++


1.滑动窗口(双指针法)+hash

一开始联想到kmp,然后发现实际还是双指针法的运用,最后看题解这也叫滑动窗口,确实和计网中的滑动窗口挺像

思路是从开始记录两个指针,第一个指针表示从它开始的最长子串长度,第二个通过移动对比前面是否出现过该字符来记录最长长度(利hash思想),len=后-前+1;

其实题目也可以开hash数组(应该更快),这里熟悉一下set,用unordered_set来做映射

时间复杂度O(n),空间O(1)

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> hash;
        int n=s.length(); 
        if(n<2)return n;
        int k=0,ans=1;
        for(int i=0;i<n;i++){
            while(k<n&&!hash.count(s[k])){
            hash.insert(s[k]);
           ans=max(ans,k-i+1);
            k++;
            }
             hash.erase(s[i]);
             if(n-i<ans)break;//剪枝
        }
        return ans;
    }
};


Python


class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        ans=0
        left=0
        right=0
        hashset=set([])
        n=len(s)
        while left<n:
            while right<n and s[right] not in hashset:
                hashset.add(s[right])
                ans=max(ans,right-left+1)
                right+=1
            hashset.remove(s[left])
            left+=1
            if n-left <ans:
                break
        return ans


java


class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> hashset=new HashSet<Character>();
        int ans=0,k=0;
        int n=s.length();
        for(int i=0;i<n;i++){
            while(k<n && hashset.contains(s.charAt(k))==false){
                hashset.add(s.charAt(k));
                ans=Math.max(ans,k-i+1);
                k++;
            }
            hashset.remove(s.charAt(i));
        }
        return ans;
    }
}
相关文章
|
12月前
|
算法 前端开发 数据处理
小白学python-深入解析一位字符判定算法
小白学python-深入解析一位字符判定算法
128 0
|
4月前
|
Java C++
力扣第一道困难题《3. 无重复字符的最长子串》,c++
首先我们看到这个题是肯定有一种暴力的硬解思路的,那就是将两个vector直接链接起来,然后再排序后,直接返回中间值,这个方法实现起来还是非常容易的,
63 0
|
7月前
|
存储 传感器 缓存
java变量与数据类型:整型、浮点型与字符类型
### Java数据类型全景表简介 本文详细介绍了Java的基本数据类型和引用数据类型,涵盖每种类型的存储空间、默认值、取值范围及使用场景。特别强调了`byte`、`int`、`long`、`float`、`double`等基本类型在不同应用场景中的选择与优化,如文件流处理、金融计算等。引用数据类型部分则解析了`String`、数组、类对象、接口和枚举的内存分配机制。
190 15
|
Python
python获取字符串()里面的字符
在Python中,如果你想获取字符串中括号(比如圆括号`()`、方括号`[]`或花括号`{}`)内的字符,你可以使用正则表达式(通过`re`模块)或者手动编写代码来遍历字符串并检查字符。 这里,我将给出使用正则表达式的一个例子,因为它提供了一种灵活且强大的方式来匹配复杂的字符串模式。 ### 使用正则表达式 正则表达式允许你指定一个模式,Python的`re`模块可以搜索字符串以查找匹配该模式的所有实例。 #### 示例:获取圆括号`()`内的内容 ```python import re def get_content_in_parentheses(s): # 使用正则表达
293 36
|
11月前
|
人工智能 Shell 开发工具
[oeasy]python0041_输出ASCII码表_英文字符编码_键盘字符_ISO_646
本文介绍了ASCII码表的生成与使用,包括英文字符、数字和符号的编码。通过Python代码遍历0到127的ASCII值,解决了找不到竖线符号的问题,并解释了ASCII码的固定映射关系及其重要性。文章还介绍了ASCII码的历史背景,以及它如何成为国际标准ISO 646。最后,通过安装`ascii`程序展示了完整的ASCII码表。
153 1
|
索引 Python
python之判断字符里面有没有|8
python之判断字符里面有没有|8
|
11月前
|
人工智能 开发工具 Python
[oeasy]python040_缩进几个字符好_输出所有键盘字符_循环遍历_indent
本文探讨了Python代码中的缩进问题。通过研究`range`函数和`for`循环,发现缩进对于代码块的执行至关重要。如果缩进不正确,程序会抛出`IndentationError`。文章还介绍了Python的PEP8规范,推荐使用4个空格进行缩进,并通过示例展示了如何使用Tab键实现标准缩进。最后,通过修改代码,输出了从0到122的字符及其对应的ASCII码值,但未能找到竖线符号(`|`)。文章在总结中提到,下次将继续探讨竖线符号的位置。
132 0
|
Python
[oeasy]python035_根据序号得到字符_chr函数_字符_character_
本文介绍了Python中的`ord()`和`chr()`函数。`ord()`函数通过字符找到对应的序号,而`chr()`函数则根据序号找到对应的字符。两者互为逆运算,可以相互转换。文章还探讨了单双引号在字符串中的作用,并解释了中文字符和emoji也有对应的序号。最后总结了`ord()`和`chr()`函数的特点,并提供了学习资源链接。
158 4
Python ASCII码与字符相互转换
Python ASCII码与字符相互转换
|
14天前
|
数据采集 机器学习/深度学习 人工智能
Python:现代编程的首选语言
Python:现代编程的首选语言
187 102

热门文章

最新文章

推荐镜像

更多