【leetcode3】 3. Longest Substring Without Repeating Characters解题报告

• 关键字：最长不重复子串、双指针
• 难度：Medium
• 题目大意：求一个字符串最长不重复子串的长度

题目：

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

Example 1:

Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:

Input: "pwwkew"
Output: 3
Explanation: 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.

思路：

使用两个指针l、r分别记录不重复子串的起始和终止位置，l、r初始值为0，使用set来放当前不重复的字符，r向右移动：

• 字符不重复时，直接将字符add到set，r继续向右移动；
• 字符重复时，l向右移动，同时set删除掉字符串l位置的字符；
• 重复上述步骤；

思路实现：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.length()==0||s==null) return 0;
        int maxLen = 1;
        int l = 0;
        int r = 1;
        Set<Character> set = new HashSet<>();
        set.add(s.charAt(l));
        while(l<s.length()&&r<s.length()) {
            if(!set.contains(s.charAt(r))) {
                set.add(s.charAt(r));
                maxLen = Math.max(maxLen, r-l+1);
                r++;
            }
            else {
                set.remove(s.charAt(l));
                l++;
            }
        }
        return maxLen;
        
    }
}