Longest Substring Without Repeating Characters

- 日理万妓 2022-08-20 05:09 14阅读 0赞

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

首先按照给出的提示用map做了一下，提示超时。

public int lengthOfLongestSubstring(String s) {
        	        if(s.length()==0)
    			return 0;
    		char sArry[] = s.toCharArray();
    		int pre = 0;
    		HashMap<Character,Integer> inMap = new HashMap<Character, Integer>();
    		for(int i=0;i<sArry.length;i++){
    			if(!inMap.containsKey(sArry[i])){
    				inMap.put(sArry[i], i);
    			}else{
    				pre = Math.max(pre, inMap.size());
    				i = inMap.get(sArry[i]);
    				inMap.clear();
    			}
    		}
    		return Math.max(pre, inMap.size());
        }

但是只有一个for循环，为什么会超时呢，下边是实现的源码。

public boolean containsKey(Object key) {
            Iterator<Map.Entry<K,V>> i = entrySet().iterator();
            if (key==null) {
                while (i.hasNext()) {
                    Entry<K,V> e = i.next();
                    if (e.getKey()==null)
                        return true;
                }
            } else {
                while (i.hasNext()) {
                    Entry<K,V> e = i.next();
                    if (key.equals(e.getKey())) 
                        return true;
                }
            }
            return false;
        }

不用Map的话，可以采用下边这个方法来做

public  int lengthOfLongestSubstring(String s) {
    	    if(s==null)
    	    	return 0;
    	    //默认状态为false，每一个字符都有一个码值
    		boolean[] flag = new boolean[256];
    
    		int result = 0;
    		int start = 0;
    		char[] arr = s.toCharArray();
    		for (int i = 0; i < arr.length; i++) {
    			char current = arr[i];
    			//再一次存在的时候
    			if (flag[current]) {
    				//将当前最大和之前最大做一个比较，取最大的保存
    				result = Math.max(result, i - start);
    				//将相同之前的数全部置为false，遍历后边的数组
    				for (int k = start; k < i; k++) {
    					if (arr[k] == current) {
    						start = k + 1; 
    						break;
    					}
    					flag[arr[k]] = false;
    				}
    			} else {
    				//存在的话置为true
    				flag[current] = true;
    			}
    		}
    		result = Math.max(arr.length - start, result);
    		return result;
    	}