LeetCode第三题之无重复字符的最长子串

「爱情、让人受尽委屈。」 2022-05-27 13:21 127阅读 0赞

给定一个字符串，找出不含有重复字符的最长子串的长度。

示例：

给定 `"abcabcbb"` ，没有重复字符的最长子串是 `"abc"` ，那么长度就是3。

给定 `"bbbbb"` ，最长的子串就是 `"b"` ，长度是1。

给定 `"pwwkew"` ，最长子串是 `"wke"` ，长度是3。请注意答案必须是一个子串，`"pwke"` 是 *子序列  *而不是子串。

思路一：直接暴力求解，把所有的可能子串遍历出来，得出长度最大的那个。

public static int lengthOfLongestSubstring1(String s) {
            int maxlength = 0;
            int strLength = s.length();
            for(int i=0;i<strLength;i++) {
            	StringBuilder sBuilder = new StringBuilder();
            	sBuilder.append(s.charAt(i));
            	for(int j=i+1;j<strLength;j++) {
            		if(sBuilder.indexOf(""+s.charAt(j))!=-1) {
            			break;
            		}else {
            			sBuilder.append(s.charAt(j));
            		}
            	}
            	maxlength = (maxlength>sBuilder.length())?maxlength:sBuilder.length();
            }
            return maxlength;
        }

思路二：空间换时间，查找重复值可以用map或者set等，这里使用hashset（底层也是hashmap）,时间复杂度O(N).

public static int lengthOfLongestSubstring2(String s) {
            int maxlength = 0;
            int strLength = s.length();
            int left=0,right=0;
            HashSet<Character> hashSet = new HashSet<>();
            while (left<strLength&&right<strLength) {
    			if(hashSet.contains(s.charAt(right))) {
    				hashSet.remove(s.charAt(left));
    				left++;
    			}else {
    				hashSet.add(s.charAt(right));
    				right++;
    				maxlength = Math.max(maxlength, right - left);
    			}
    		}
            return maxlength;
        }

思路三：以上两个方法都是一个一个的遍历，其实中间可以省掉很多步，当查到第一个重复字符时，最外层再次查询的时候可以从第一个重复字符的下一个开始。例如，给定字符串“abcbdc”,当查到b这个重复字符时，下一次遍历可以直接从d开始。

public static int lengthOfLongestSubstring3(String s) {
    		int maxlength = 0;
    		int strLength = s.length();
    		HashMap<Character, Integer> hashMap = new HashMap<>();
    		int left=0,right=0;
    		while (left<strLength&&right<strLength) {
    			if(hashMap.containsKey(s.charAt(right))) {
    				left = Math.max(hashMap.get(s.charAt(right))+1, left);
    			}
    			hashMap.put(s.charAt(right), right);
    			right++;
    			maxlength = Math.max(maxlength, right - left);
    		}
    		return maxlength;
    	}

GitHub地址： [https://github.com/xckNull/Algorithms-introduction][https_github.com_xckNull_Algorithms-introduction]

[https_github.com_xckNull_Algorithms-introduction]: https://github.com/xckNull/Algorithms-introduction