字符串中查找最大连续不重复字符串(Longest Substring Without Repeating Characters)__By leetCode

向右看齐 2022-05-16 00:39 16阅读 0赞

> ###  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
> 
> 查找一个字符中最大连续不重复字符串

*  One

public int lengthOfLongestSubstring(String s) {
            Set<Character> set = new HashSet<>();
    
            char[] charList = s.toCharArray();
    
            int length = 0;
            int sum =0;
            for (int i = 0,j=0; i < charList.length; i++) {
                if (set.contains(charList[i])){
                    sum = set.size();
                    set.clear();
                    j++;
                    i = j;
                    set.add(charList[j]);
                    length = Math.max(length , sum);
                }else {
                    set.add(charList[i]);
                    if (i == charList.length-1){
                        sum = set.size();
                        length = Math.max(length , sum);
                    }
                }
            }
    
            return length;
        }

> 解析:  
> 创建一个HashSet，存储对应字符，然后返回最大长度.

*  Two

public int lengthOfLongest(String s){
            int n = s.length(), ans = 0;
    
            int[] index= new int[128];
    
            for (int current = 0,start=0; current < n; i++) {
                start = Math.max(index[s.charAt(current)],start);
                ans = Math.max(ans ,current-start+1);
                index[s.charAt(current)] = current+1;
            }
            return ans;
        }

> 解析:  
> 用start标注重复字符的下一个起始位置，然后用current+1标注当前位置，current+1-start就是此次循环最大值。

*  备注
 *  int\[26\] for Letters ‘a’ - ‘z’ or ‘A’ - ‘Z’
 *  int\[128\] for ASCII
 *  int\[256\] for Extended ASCII