003. 无重复最长子串

中等

解法一：暴力解法

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int len = s.length();
        int [] a = new int[len];
        for(int i = len;i > 0;i--){
            for(int j = 1;j <= len+1-i;j++){
                String str = s.substring(j-1,j-1+i); // 获取截取字符串
                HashSet set = new HashSet();
                for(int k = 0;k < i;k++){
                    set.add(str.charAt(k)); // 遍历存入set中
                    if(set.size() != k+1){
                        break;
                    }else if(set.size() == i){
                        return i;
                    }
                }
            }
        }
        return 0;
    }
}

解法思路：

从大到小获取字符串的所有子串，将子串存入 HashSet 中，若 HashSet 的长度与子串长度相等，返回 HashSet 的长度。此算法的时间复杂度为 O(n³)

解法二：滑动窗口

class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashSet<Character> set = new HashSet<>();
        int left = 0;
        int right = 0;
        int res = 0;  // 左右边界的距离
        if(s.length() <= 1){ // 字符串特殊长度
            return s.length();
        }else {
            while(right < s.length()){
                while(set.contains(s.charAt(right))){
                    set.remove(s.charAt(left));
                    left++;
                }
                set.add(s.charAt(right));
                right++;
                if((right - left) > res){
                    res = right - left;
                }
            }
            return res;
        }
    }
}

解法思路：

建立 left 和 right 两个数，记录窗口的左右边界和距离 res=(right-left)，建立一个 Hashset，存储 left 和 right 之间的字符，移动 right，并循环判断 map 中是否包含 right 所指字符，如果有，去除 left 指向字符，循环上述操作，记录最大的 res 并返回，该算法的平均时间复杂度为 O(n²)。

滑动窗口的优化：

Java

class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashMap map = new HashMap();
        int left = 0;
        int right = 0;
        int res = 0;
        if(s.length() <= 1){
            return s.length();
        }else {
            while(right < s.length()){
                int i = (int)map.getOrDefault(s.charAt(right),-1);//Map中会存储一一对应的key和value。，如果 在Map中存在key，则返回key所对应的的value。如果 在Map中不存在key，则返回默认值。
                if(i >= left){
                    left = i + 1;
                }
                map.put(s.charAt(right),right);
                right++;
                if((right - left) > res){
                    res = right - left;
                }
            }
            return res;
        }
    }
}

Python

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left = 0
        right = 1
        s_len = len(s)
        if(s_len <= 1): return s_len
        d = dict()
        d[s[left]] = left
        res = 1
        while (right < s_len):
            if(s[right] in d):
                res = max(len(d),res)
                idx = d.get(s[right])
                for i in range(left , idx + 1):
                    d.pop(s[i])
                left = idx + 1
                d[s[right]] = right
                right += 1
            else:
                d[s[right]] = right
                right += 1
                res = max(res,len(d))
        return res