字符串的最長無重復(fù)字符的子串長度是什么

本篇文章給大家分享的是有關(guān)字符串的最長無重復(fù)字符的子串長度是什么，小編覺得挺實(shí)用的，因此分享給大家學(xué)習(xí)，希望大家閱讀完這篇文章后可以有所收獲，話不多說，跟著小編一起來看看吧。

題目描述：

對于一個字符串,請?jiān)O(shè)計(jì)一個高效算法，找到字符串的最長無重復(fù)字符的子串長度。

給定一個字符串A及它的長度n，請返回它的最長無重復(fù)字符子串長度。保證A中字符全部為小寫英文字符，且長度小于等于500。

測試樣例：

"abcdbefgdchi",12

返回：8

這個題我研究了好半天，確實(shí)不好想，看了別人的思路，半天才把代碼寫出來

分析：

首先定義三個輔助變量：

max_len：表示字符串中最長無重復(fù)字符的子串長度，也就是函數(shù)返回值

map<char, int>：用來存放當(dāng)字符串前位置的字符最近出現(xiàn)的位置

pre_len：用來存放當(dāng)前位置之前最長無重復(fù)字符的子串長度

下面開始主邏輯

從字符串的起始處開始遍歷

如果map中沒有該字符，則將該字符及其下標(biāo)插入到map中，并將pre_len++

再和max_len進(jìn)行比較，取較大者賦給max_len

如果map中已經(jīng)有了該字符，那么取出該字符對應(yīng)的值（也就是該字符最近出現(xiàn)的下標(biāo)）記為pos_A

當(dāng)前下標(biāo)減去pre_len記為pos_B，表示前面最長無重復(fù)字符子串的起始位置

這時候，pos_A和pos_B會有一下三種情況：

第一種情況：posA == pos_B

第二種情況：pos_A > pos_B

第三種情況：pos_A < pos_B

對于第一種情況來說，pre_len 大小不會改變。

對于第二種情況來說，pos_A 在 pos_B的右邊，根據(jù) pos_A 和 pos_B 所代表的含義可知道：

在距離當(dāng)前很近的位置上，當(dāng)前字符已經(jīng)出現(xiàn)了重復(fù)，因此當(dāng)前位置之前最長無重復(fù)字符子串的長度縮短了，如圖所示：

因此，更新后的 pre_len 應(yīng)該為 當(dāng)前位置的下標(biāo)減去 pos_A

對于第三種情況來說，pos_A 在 pos_B 的左邊，根據(jù) pos_A 和 pos_B 所代表的含義可知道：

在距離當(dāng)前很遠(yuǎn)的位置上，當(dāng)前字符出現(xiàn)了重復(fù)，這個位置比pos_B 還遠(yuǎn)，這么遠(yuǎn)的路徑上，pos_B 處的字符早已出現(xiàn)了重復(fù)，因此當(dāng)前位置之前最長無重復(fù)字符子串的長度應(yīng)該為 當(dāng)前位置到pos_A 的距離，如圖所示

因此，更新后的 pre_len 應(yīng)該為 當(dāng)前位置的下標(biāo)減去 pos_B + 1

更新后的pre_len 與max_len 進(jìn)行比較，取其大者即可

注意，最后應(yīng)該將map中當(dāng)前位置字符的下標(biāo)進(jìn)行更新（千萬不能漏掉）

于是乎一個完整的邏輯已經(jīng)完成了，這樣從頭到尾遍歷這個字符串，最終便可得到

字符串的最長無重復(fù)字符的子串長度 max_len

甚至還可以獲得該字串，將其單獨(dú)打印出來（這里留給讀者自行實(shí)現(xiàn)，不難）

代碼如下：

int longestSubstring(string A, int n) {
	if (A.size() <= 0 || n <= 0)
		return 0;

	int max_len = -1;
	int pre_len = 0;
	map<char, int> m;
	for (int i = 0; i < A.size(); ++i){
		if (m.count(A[i]) == 0){
			m.insert(pair<char, int>(A[i], i)); //map中不存在該字符，則直接插入
			++pre_len;
			if (pre_len > max_len)
				max_len = pre_len;
			continue;
		}
	
		map<char, int>::iterator iter_prev = m.find(A[i]);
		int pos_A = iter_prev->second;
		int pos_B = i - pre_len;
		
		if (pos_A > pos_B)
		{
			pre_len = i - pos_A;
		}
		else if (pos_B > pos_A)  //pos_A <= pos_B
		{
			pre_len = i - pos_B + 1;
		}
		else
		{
			//do nothing!
		}

		if (pre_len > max_len)
			max_len = pre_len;

		m[A[i]] = i;  //更新map
	}

	return max_len;
}

以上就是字符串的最長無重復(fù)字符的子串長度是什么，小編相信有部分知識點(diǎn)可能是我們?nèi)粘９ぷ鲿姷交蛴玫降?。希望你能通過這篇文章學(xué)到更多知識。更多詳情敬請關(guān)注億速云行業(yè)資訊頻道。