算法1

(暴力枚举) $O(n^2)$

从每个节点开始遍历
把结果始终维护在一个set中，遇到重复的就将它清空，遍历以下一个字符为开始的不重复子串

时间复杂度

参考文献

java代码

lass Solution {
    public int lengthOfLongestSubstring(String s) {
        //时间复杂度为O(n*n)
        int ans = 0;
        HashSet<Character> ms= new HashSet<>();
        for(int i=0;i<s.length();i++){
            for(int j = i;j<s.length();j++){
                if(ms.contains(s.charAt(j))) break;
                else{
                    ms.add(s.charAt(j));
                }
            }
            ans = Math.max(ans,ms.size());
            ms.clear();
        }
        return ans;
    }
}

算法2

(滑动窗口) $O(n)$

• 用滑动窗口来进行改良，因为在遍历到第i个字符时，它到第j个字符是不重复的，那么从第i+1开始到第j个也一定不重复，所以从i+1开始的一定是j+…；
• 我们遍历到下一个元素时，它若是重复字符，那么在它前一次出现之前的所有元素都不需要进行遍历了，我们用hashMap来记录字符和字符出现的位置。

时间复杂度

参考文献

java 代码

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.length()<=1) return s.length();
        //时间复杂度为O(n)，每个节点只遍历一遍，空间复杂度是O(n),
        int ans = 0;
        HashMap<Character,Integer> ms= new HashMap<>();
        int i = 0;
        ms.put(s.charAt(0),0);
        int j = 1;
        while(j<s.length()){
            if(ms.get(s.charAt(j))!=null)
            {
                ans = Math.max(ans,j-i);//只在一个分支了计算了长度，有可能就一直进不去##
                i = Math.max(ms.get(s.charAt(j))+1,i);
            }
            ms.put(s.charAt(j),j);
            j++;
        }
        return Math.max(ans,j-i);//特判了##这种情况
    }