3. Longest Substring Without Repeating Characters（计算不含重复字符的最长子串的长度）

今天药忘吃喽~ 2022-06-09 12:10 181阅读 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 and not a substring.

**题目大意：**给定一个字符串，计算出不含重复字符的最长子串的长度。例如"pwwkew"满足条件的最长子串是"wke"而不是"pwke"，因为要是连续的子串，而不是子序列。  
  
  
**解题思路：**maxLen代表当前已经找到的满足条件的最长子串的长度，两个int指针start和end，s\[start\]至s\[end-1\]表示当前已经遍历到的不含重复字符的子串，s\[end\]表示当前正在遍历的字符：  
  
  
                  如果s\[end\]包含在s\[start\]至s\[end-1\]的子串中，那么找到与s\[end\]重复的那个字符的位置，将start移动到这个位置+1的位置，并将end++然后继续遍历;  
  
  
                  如果不包含的话，那么这时候将end-start+1与maxLen比较，如果大于maxLen，那么替换maxLen。然后end++并继续遍历。  
  
  
                  直到end的值超出字符串的长度范围。

**解题代码：**（53ms，beats 70.53%）

class Solution {
        public int lengthOfLongestSubstring(String s) {
            if (s.length() < 2) {
    			return s.length();
    		}
    		int maxLen = 1, start = 0, end = 1, len = 1;
    		String curStr;
    		while (end < s.length()) {
    			curStr = s.substring(start, end);
    			if (curStr.contains(String.valueOf(s.charAt(end)))) {
    				start = s.indexOf(s.charAt(end), start) + 1;
    				end++;
    				continue;
    			}
    			len = end - start + 1;
    			if (len > maxLen) {
    				maxLen = len;
    			}
    			end++;
    		}
    
    		return maxLen;
        }
    }