LeetCode Longest Substring Without Repeating Characters（滑动窗口裸题）

柔光的暖阳◎ 2022-03-19 15:37 106阅读 0赞

[https://leetcode.com/problems/longest-substring-without-repeating-characters/][https_leetcode.com_problems_longest-substring-without-repeating-characters]

题意：求出所给字符串的最长非重复子串（注意是子串，而不是子序列）

思路：很简单的思路就是从左往右扫描，利用一个队列来存储扫描过的字符，如果当前字符之前已经出现过了，则不断将队首元素弹出，直到里面没有和新元素相同的，再将新元素加进去。复杂度的下限必然是o(n),上限取决于你怎么做判断。

这题如果我用c++写必然是o(n^2)了，但是最后用了java，然后告诉我java字典的查找是o(1)的？？？

public class Solution {
        public int lengthOfLongestSubstring(String s) {
            int n=s.length();
            Set<Character> se = new HashSet<>();
            int M=0,i=0,j=0;
            while(i<n&&j<n){
                if(!se.contains(s.charAt(j))){
                    se.add(s.charAt(j++));
                    M=Math.max(M,j-i);
                }
                else{
                    se.remove(s.charAt(i++));
                }
            }
            return M;
        }
    }

另一种思路应该是找个map来保存已经出现过的字符。最后复杂度可以到o(n).

[https_leetcode.com_problems_longest-substring-without-repeating-characters]: https://leetcode.com/problems/longest-substring-without-repeating-characters/

发表评论取消回复

表情：

评论列表（有 0 条评论，106人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCod-3. Longest Substring Without Repeating Characters

Problem: Given a string, find the length of the longest substring without repeating

ゞ浴缸里的玫瑰/ 2022年08月21日 12:53/ 0 赞/ 133 阅读

相关 Longest Substring Without Repeating Characters

Longest Substring Without Repeating Characters Given a string, find the length of the

快来打我*/ 2022年08月06日 10:18/ 0 赞/ 107 阅读

相关 leetcode Longest Substring Without Repeating Characters

题目 Given a string, find the length of the longest substring without repeating charact

墨蓝/ 2022年08月05日 00:51/ 0 赞/ 117 阅读

相关 LeetCode：Longest Substring Without Repeating Characters

第三题寻找最大的不包含重复字符的字符串。借助了python的str查找函数，应该不是最优的解法。 ! /usr/bin/env python -

谁践踏了优雅/ 2022年07月12日 07:42/ 0 赞/ 102 阅读

相关 Leetcode——3. Longest Substring Without Repeating Characters

1. 概述 Given a string, find the length of the longest substring without repeating char

桃扇骨/ 2022年06月15日 10:36/ 0 赞/ 141 阅读

相关 LeetCode3—Longest Substring Without Repeating Characters

本类型博客中的各算法的时间复杂度分析均为博主自己推算，本类型博客也是博主自己刷LeetCode的自己的一些总结，因此个中错误可能较多，非常欢迎各位大神在博客下方评论，请不吝赐教

刺骨的言语ヽ痛彻心扉/ 2022年06月09日 07:38/ 0 赞/ 128 阅读

相关 Longest Substring Without Repeating Characters

题目 Given a string, find the length of the longest substring without repeating char

短命女/ 2022年06月08日 11:46/ 0 赞/ 156 阅读

相关 Longest Substring Without Repeating Characters

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

冷不防/ 2022年06月08日 08:13/ 0 赞/ 95 阅读

相关 LeetCode Longest Substring Without Repeating Characters（滑动窗口裸题）

[https://leetcode.com/problems/longest-substring-without-repeating-characters/][https_le

柔光的暖阳◎/ 2022年03月19日 15:37/ 0 赞/ 107 阅读

相关 Longest Substring Without Repeating Characters

题意为给出一个字符串，找出其中没有重复字符的最长子序列的长度。brute force的复杂度为O(n^3).依次查找每个子字符串是否含有重复字符，并比较长度。开始看到题目，想用

淡淡的烟草味﹌/ 2021年12月17日 10:27/ 0 赞/ 105 阅读