题目描述

blablabla

样例

blablabla

算法1

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

暴力做法，以每一个字母为终点的最大的不重复子串，用hash表来做

时间复杂度

参考文献

java 代码

class Solution {
    public int longestSubstringWithoutDuplication(String s) {
        //暴力做法，以每一个字母为终点的最大的不重复子串，用hash表来做
        //双指针单调，后一个指针j往后扫的时候，前一个指针i是从当前位置开始走的
        HashMap<Character,Integer> mp = new HashMap<>();//存放字符串值的
        int res=0;//结果
        //暴力解法
        int n =s.length();
        for(int j=0;j<n;j++)//以每一位为截止的最长子串
        {
            int i;
            for(i=j;i>=0;i--)
            {
                if(mp.get(s.charAt(i))==null) mp.put(s.charAt(i),1);
                else break;
            }
            res=res>mp.size()?res:mp.size();
            mp.clear();
        }
        return res;
    }
}

算法2

(改进版) $O(n)$

暴力解法会重复的将不重复的字母加到hashMap中，然后再删除掉；
j是最长不重子串的右端点,i是最长不重子串的左端，
i的更新：当出现重复，将i往后走，走到重复的节点为止，删掉走过的所有节点

时间复杂度

参考文献

java 代码

class Solution {
    public int longestSubstringWithoutDuplication(String s) {
        //暴力做法，以每一个字母为终点的最大的不重复子串，用hash表来做
        //双指针单调，后一个指针j往后扫的时候，前一个指针i是从当前位置开始走的
        HashMap<Character,Integer> mp = new HashMap<>();//存放字符串值的
        int res=0;//结果
        //暴力解法
        int n =s.length();
        for(int i=0,j=0;j<n;j++)
        {
            char p =s.charAt(j);
          if(mp.get(p)!=null)
          {
              do{
                  mp.remove(s.charAt(i));
              }while(s.charAt(i++)!=p);
          }
            mp.put(p,1);
            res=res>mp.size()?res:mp.size();
        }
        return res;
    }
}