Leetcode 3. Longest Substring Without Repeating Characters

简介: 此题题意是找出一个不包含相同字母的最长子串,题目给出了两个例子来说明题意,但这两个例子具有误导性,让你误以为字符串中只有小写字母。还好我是心机boy,我把大写字母的情况也给考虑进去了,不过。。。。字符串里竟然有特殊字符,于是贡献了一次wrong answer,这次我把ascii字符表都考虑进去,然后就没问题了。这个故事告诫我们在编程处理问题的时候一定要注意输入数据的范围,面试中可以和面试官去确认数据范围,也能显得你比较严谨。

Given a string, find the length of the longest substring without repeating characters.


原题链接:Longest Substring Without Repeating Characters


 此题题意是找出一个不包含相同字母的最长子串,题目给出了两个例子来说明题意,但这两个例子具有误导性,让你误以为字符串中只有小写字母。还好我是心机boy,我把大写字母的情况也给考虑进去了,不过。。。。字符串里竟然有特殊字符,于是贡献了一次wrong answer,这次我把ascii字符表都考虑进去,然后就没问题了。这个故事告诫我们在编程处理问题的时候一定要注意输入数据的范围,面试中可以和面试官去确认数据范围,也能显得你比较严谨。

 这题也有笨方法解的,就是枚举所有子串,然后再判断其中是否包含相同字符,假设字符串长度是n,很明显枚举的时间复杂度是O(n^2)。如果你真在面试中遇到了此题,暴力枚举的方法绝对不会是正确答案,所以我们还需要深入思考下。 实话告诉你,我这里有O(n)的解法。

 如果字符串中仅限小写字母,很显然,任何情况下这个包含不重复字符的子串最长不会超过26,我就不信你不知道为啥。 首先个小技巧,如果最快的判断一个字符是否在字符串中存在过了——当然是用一个数组记录下这个字符出现的次数,而不是遍历一遍字符串,我代码中cnt数组就是来做这事的。 我用两个变量 start和end来表示子串的起始和末尾位置,cnt数组来表示start和end之间各个字符有多少个。

 最重要的地方来了,当我遍历到原字符某个位置(我表示为end)的时候,如果end位置的字符(str[end])在cnt数组中为0,那么意味着我把str[end]加入子串中(也就是cnt[str[end]]++),该子串依旧是不包含重复字符的。 相反,如果start到end-1之间的子串已经包含字符str[end]的时候,我就把start的位置往后挪(start++),直到start到end-1表示的子串不包含str[end]这个字符。 我只需要一直保证start到end之间不包含重复字符就好了,然后取最大的end-start就是我们需要的答案了。

 以下就是我的解题代码,击败了85.63%的java代码,别看有三个while,两层的while循环,时间复杂度确确实实只有O(n)

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (null == s)
            return 0;
        int len = s.length();
        int start = 0, end = 0;
        int[] cnt = new int[130];
        int ans = 0;
        while (end < len) {
            while (cnt[s.charAt(end)] > 0 && start < len) {
                cnt[s.charAt(start)]--;
                start++;
            }
            while (end < len && cnt[s.charAt(end)] == 0) {
                cnt[s.charAt(end)]++;
                end++;
            }
            if (end - start > ans)
                ans = end - start;
        }
        return ans;
    }
    public static void main(String[] args) {
        String str = "p$%^&*(*&^%$#$%^&*(";
        Solution s = new Solution();
        System.out.println(s.lengthOfLongestSubstring(str));
    }
}
目录
打赏
0
3
3
0
13
分享
相关文章
Leetcode 516. Longest Palindromic Subsequence
找到一个字符串的最长回文子序列,这里注意回文子串和回文序列的区别。子序列不要求连续,子串(substring)是要求连续的。leetcode 5. Longest Palindromic Substring就是求连续子串的。
63 0
LeetCode 1160. 拼写单词 Find Words That Can Be Formed by Characters
LeetCode 1160. 拼写单词 Find Words That Can Be Formed by Characters
LeetCode 1160. 拼写单词 Find Words That Can Be Formed by Characters
LeetCode 424. Longest Repeating Character Replacem
给你一个仅由大写英文字母组成的字符串,你可以将任意位置上的字符替换成另外的字符,总共可最多替换 k 次。在执行上述操作后,找到包含重复字母的最长子串的长度。
114 0
LeetCode 424. Longest Repeating Character Replacem
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
101 1
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
6月前
|
【Leetcode刷题Python】1467. 两个盒子中球的颜色数相同的概率
本文介绍了LeetCode第50题"Pow(x, n)"的解法,题目要求实现计算x的n次幂的函数,文章提供了递归分治法的详细解析和Python实现代码。
76 0
|
6月前
|
【Leetcode刷题Python】50. Pow(x, n)
本文介绍了LeetCode第50题"Pow(x, n)"的解法,题目要求实现计算x的n次幂的函数,文章提供了递归分治法的详细解析和Python实现代码。
38 1
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
147 2
|
6月前
|
【Leetcode刷题Python】73. 矩阵置零
本文介绍了LeetCode第73题的解法,题目要求在给定矩阵中将所有值为0的元素所在的行和列全部置为0,并提供了一种原地算法的Python实现。
55 0
【Leetcode刷题Python】73. 矩阵置零
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等