LeetCod-3. Longest Substring Without Repeating Characters

ゞ浴缸里的玫瑰 2022-08-21 12:53 130阅读 0赞

Problem:

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.
    
    Subscribe to see which companies asked this question

Analysis:

题意：

*  给定一个字符串，找到其中的一个最长的字串，使得这个子串不包含重复的字符。

方法：

1.  利用双指针，开一个数组记录当前字符最近出现的位置，一遍算过去，更新左边界，用它计算最大值就行了。时间复杂度O(n),空间复杂度O(1).

Answer:

public class Solution {
        public int lengthOfLongestSubstring(String s) {
            int res=0,left=0;
            int[] arr = new int[128];
            for(int i=0;i<arr.length;i++){
                arr[i]=-1;
            }
            for(int i=0;i<s.length();i++){
                char temp = s.charAt(i);
                if(arr[temp]>=left)
                    left = arr[temp]+1;
                arr[temp]=i;
                if(res< i-left+1) 
                    res = i-left+1;
            }
            return res;
        }
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 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 赞/ 131 阅读

相关 LeetCode(3) Longest Substring Without Repeating Characters

LeetCode的第3题，给定一个字符串，找到其中的一个最长的字串，使得这个子串不包含重复的字符。 Given a string S, find the longest p

蔚落/ 2022年07月17日 15:26/ 0 赞/ 103 阅读

相关 [leetcode]3. Longest Substring Without Repeating Characters

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

╰+攻爆jí腚メ/ 2022年06月18日 06:11/ 0 赞/ 88 阅读

相关 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 赞/ 138 阅读

相关 LeetCode3—Longest Substring Without Repeating Characters

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

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

相关 LeetCode 3. Longest Substring Without Repeating Characters

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

╰半橙微兮°/ 2022年05月27日 07:50/ 0 赞/ 114 阅读

相关 leetcode--3.Longest Substring Without Repeating Characters

public int lengthOfLongestSubstring(String s) { if(s.length()<=1){

小鱼儿/ 2022年03月28日 13:57/ 0 赞/ 157 阅读

相关【LeetCode】3. Longest Substring Without Repeating Characters

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

Myth丶恋晨/ 2022年03月15日 12:26/ 0 赞/ 124 阅读

相关 Leetcode 3. Longest Substring Without Repeating Characters

https://leetcode.com/problems/longest-substring-without-repeating-characters/ Given a s

超、凢脫俗/ 2021年12月22日 00:55/ 0 赞/ 145 阅读

相关 Leetcode3 Longest Substring Without Repeating Characters

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

阳光穿透心脏的1/2处/ 2021年10月14日 04:58/ 0 赞/ 203 阅读