java如何求無重復(fù)字符的最長(zhǎng)子串

這篇文章將為大家詳細(xì)講解有關(guān)java如何求無重復(fù)字符的最長(zhǎng)子串，小編覺得挺實(shí)用的，因此分享給大家做個(gè)參考，希望大家閱讀完這篇文章后可以有所收獲。

無重復(fù)字符的最長(zhǎng)子串

給定一個(gè)字符串，請(qǐng)你找出其中不含有重復(fù)字符的 最長(zhǎng)子串 的長(zhǎng)度。

提示：

0 <= s.length <= 5 * 104 s 由英文字母、數(shù)字、符號(hào)和空格組成

力扣鏈接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters

示例 1:

輸入 s = "abcabcbb" 輸出: 3 解釋: 因?yàn)闊o重復(fù)字符的最長(zhǎng)子串是 "abc"，所以其長(zhǎng)度為 3。

示例 2:

輸入: s = "bbbbb" 輸出: 1 解釋: 因?yàn)闊o重復(fù)字符的最長(zhǎng)子串是 "b"，所以其長(zhǎng)度為 1。

示例 3:

輸入: s = "" 輸出: 0

/*
		String s = "abcabcffhbb"; 
		//string   a b c a b c f f h b b 
		//map      0 1 2 3 4 5 6 7 8 9 10 map記錄字符最后一次出現(xiàn)的位置，(a,0)->(a,3)
		//[ ]      1 2 3 3 3 3 4 1 2 3 1  記錄s.toCharArray()數(shù)組對(duì)應(yīng)字符的最大子串長(zhǎng)度
*/

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.length() == 0){
            return 0;
        }
        char[] arr = s.toCharArray();
        int len = s.length();
		// 記錄字符最后一次出現(xiàn)的位置
		Map<Character, Integer> map_index = new HashMap<Character, Integer>();
		// 記錄s.toCharArray()數(shù)組對(duì)應(yīng)字符的最大子串長(zhǎng)度
		int[] distance = new int[len];
		map_index.put(arr[0],0);
		distance[0] = 1;
        int max = 1;
		int index;
		for(int i=1;i<len;i++) {
             // 如果map_index中已經(jīng)記錄了該字符
			if (map_index.containsKey(arr[i])) {
                  // 得到該字符上次出現(xiàn)的下標(biāo)
				index = map_index.get(arr[i]);
                  // 前一個(gè)字符的最長(zhǎng)子串+1 與 相同字符的距離進(jìn)行比較，選擇較小值(才沒有重復(fù)的字符)。
				distance[i] = (distance[i-1]+1) < (i - index)?(distance[i] = distance[i-1]+1):(i-index);
			}else {
                  // 前面沒有出現(xiàn)該字符直接+1即可
				distance[i] = distance[i-1] +1;
			}
            max = Math.max(max,distance[i]);
			map_index.put(arr[i], i);
		}
		return max;
    }
}

使用了數(shù)組記錄字符串中每個(gè)字符對(duì)應(yīng)的最大子串長(zhǎng)度，map則是記錄某個(gè)字符最后一次出現(xiàn)的位置。用前一個(gè)字符+1與相同字符的距離進(jìn)行比較，求出不重復(fù)的子串長(zhǎng)度。

關(guān)于“java如何求無重復(fù)字符的最長(zhǎng)子串”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，使各位可以學(xué)到更多知識(shí)，如果覺得文章不錯(cuò)，請(qǐng)把它分享出去讓更多的人看到。