LeetCode-Longest Substring Without Repeating Characters-白红宇

LeetCode-Longest Substring Without Repeating Characters

阅读量：7124 次

发布时间：2019-06-28

本文共 3849 字，大约阅读时间需要 12 分钟。

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

这道题考察如何维护一个window。

1 public class Solution { 2    public static int lengthOfLongestSubstring(String s) { 3         if(s == null || s.length()==0){ 4             return 0; 5         } 6          7         int len = s.length();     8         int l = 0; 9         int r = 1;10         int maxLength = 1;11        12         13         HashSet
     
       set = new HashSet
      
       ();14         set.add(s.charAt(l));15         16         while(r < len){17             if(!set.contains(s.charAt(r))){18                 set.add(s.charAt(r));19                 r ++;         20                 maxLength = Math.max(maxLength, r-l);21                 22                 if(r == len){23                     return maxLength;24                 }25                 26             }27             else{28                 while(s.charAt(l) != s.charAt(r)){29                     set.remove(s.charAt(l));30                     l ++;31                 }32                 l ++;33                 r ++;   34                 if(r == len){35                     return maxLength;36                 }37             }38             39         }40         41         return maxLength;42     }43 }

另一种可以通过OA 的方法：

class Solution {    public int lengthOfLongestSubstring(String s) {        if(s == null || s.length() == 0){            return 0;        }        int res = 1;        for (int i=0; i
     
       map = new HashMap();            for (int j = i; j < s.length(); j++){                char c = s.charAt(j);                if(!map.containsKey(c)){                    cursor++;                    map.put(c, 1);                }                else{                    break;                }            }            if(cursor > res){                res=cursor;            }         }        return res;    }}

　　利用hashmap存储不重复子串，key为字符，value为此字符的位置。从前向后进行遍历，只要map 中没有当前字符，便将其加入map 。并将子串长度加一。若当前字符已经出现在map 中，获得map中此字符的位置，清除此位置以及之前的的所有key 。从此位置之后重新计算子串，保证了子串的不重复。

class Solution {    public int lengthOfLongestSubstring(String s) {        if(s == null || s.length() == 0){            return 0;        }        Map
     
       map = new HashMap<>();        int start = 0;        int maxLen = 0;        int curLen = 0;        for(int i=0; i
      
       maxLen){                    maxLen = curLen;                }                map.put(c, i);            }            else{                int index = map.get(c);                for(int j = start; j<=index; j++){                    map.remove(s.charAt(j));                }                map.put(c, i);                start = index+1;                curLen = i - index;            }                    }        return maxLen;    }}

　　二刷：

class Solution {    public int lengthOfLongestSubstring(String s) {        if(s == null || s.length() == 0){            return 0;        }        Map
     
       map = new HashMap<>();        int left = 0, right = 0;        int max = 0, temp = 0;                while(right < s.length()){            if(!map.containsKey(s.charAt(right))){                temp++;                if(temp > max){                    max = temp;                }            }            else{                for(int i = left; i < map.get(s.charAt(right)); i++){                    map.remove(s.charAt(i));                }                left = map.get(s.charAt(right))+1;                temp = right - map.get(s.charAt(right));            }            map.put(s.charAt(right), right);            right++;        }        return max;    }}

转载于:https://www.cnblogs.com/incrediblechangshuo/p/4446140.html

你可能感兴趣的文章