作者推薦

【二叉樹】【單調(diào)雙向隊列】LeetCode239:滑動窗口最大值

本文涉及的基礎(chǔ)知識點

C++算法：滑動窗口總結(jié)

題目

給你一個字符串 s 、一個字符串 t 。返回 s 中涵蓋 t 所有字符的最小子串。如果 s 中不存在涵蓋 t 所有字符的子串，則返回空字符串 “” 。
注意：
對于 t 中重復(fù)字符，我們尋找的子字符串中該字符數(shù)量必須不少于 t 中該字符數(shù)量。
如果 s 中存在這樣的子串，我們保證它是唯一的答案。
示例 1：
輸入：s = “ADOBECODEBANC”, t = “ABC”
輸出：“BANC”
解釋：最小覆蓋子串 “BANC” 包含來自字符串 t 的 ‘A’、‘B’ 和 ‘C’。
示例 2：
輸入：s = “a”, t = “a”
輸出：“a”
解釋：整個字符串 s 是最小覆蓋子串。
示例 3:
輸入: s = “a”, t = “aa”
輸出: “”
解釋: t 中兩個字符 ‘a(chǎn)’ 均應(yīng)包含在 s 的子串中，
因此沒有符合條件的子字符串，返回空字符串。
參數(shù)范圍：
m == s.length
n == t.length
1 <= m, n <= 10⁵
s 和 t 由英文字母組成

滑動窗口

** 時間復(fù)雜度** : O(n+m)。兩層循環(huán)，分別枚舉子數(shù)組起點和終點[i,right)，由于right不歸0，所以總時間復(fù)雜度是O(n)。

CContain

m_mNeedCharCount記錄了t中各字符的數(shù)量，m_mHasCharCount記錄了枚舉的子串各字符的數(shù)量。m_iNotSameCharCount 記錄了m_mHasCharCount有多少個字符的數(shù)量少于m_mNeedCharCount。m_iNotSameCharCount為0，表示此子串符合題意。

iAdd可以為1或-1
將m_iNotSameCharCount改名m_iLessCharCount更符合題意。

滑動窗口

CContain 記錄[i,right1)，讓它記錄[i,right1+1)，只需要將s[right1]加進去就可以了。
CContain 記錄[i,right1)，讓它記錄[i+1,right1)，只需要減去s[i]就可以了。
[i,right) 是符合題意的最小值，也就是[i,right-1)不符合題意，[i+1,right-1)也必定不符合題意。所以無需嘗試[i+1,right-1)。即right無需歸0（復(fù)位）。

代碼

核心代碼

class CContain
{
public:
	CContain(const string& t)
	{
		for (const auto& ch : t)
		{
			m_mNeedCharCount[ch]++;
		}
		m_iNotSameCharCount = m_mNeedCharCount.size();
	}
	void Add(const char& ch,int iAdd)
	{
		if (m_mNeedCharCount.count(ch)&&(m_mHasCharCount[ch] >= m_mNeedCharCount[ch] ))
		{
			m_iNotSameCharCount++;
		}
		m_mHasCharCount[ch] += iAdd;
		if (m_mNeedCharCount.count(ch) && (m_mHasCharCount[ch] >= m_mNeedCharCount[ch]))
		{
			m_iNotSameCharCount--;
		}
	}
	bool IsAllContain()
	{
		return 0 == m_iNotSameCharCount;
	}
protected:
	std::unordered_map<char, int> m_mNeedCharCount, m_mHasCharCount;
	int m_iNotSameCharCount = 0;
};
class Solution {
public:
	string minWindow(string s, string t) {
		CContain test(t);
		int iMaxLen = INT_MAX;
		int iPos =0;
		for (int i = 0, right = 0; i < s.length(); i++)
		{
			for(;(right < s.length())&&(!test.IsAllContain());right++)
			{
				test.Add(s[right],1);
			}
			if (test.IsAllContain())
			{
				if (right - i < iMaxLen)
				{
					iMaxLen = right - i;
					iPos = i;
				}
			}
			test.Add(s[i], -1);
		}
		if (INT_MAX == iMaxLen)
		{
			iMaxLen = 0;
		}
		return s.substr(iPos, iMaxLen);
	}
};

測試用例

template<class T>
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}
}
int main()
{
	string s,t;
	{
		Solution sln;
		s = "a", t = "a";
		auto res = sln.minWindow(s, t);
		Assert(std::string("a"), res);
	}
	{
		Solution sln;
		s = "ADOBECODEBANC", t = "ABC";
		auto res = sln.minWindow(s, t);
		Assert(std::string("BANC"), res);
	}
	
	{
		Solution sln;
		s = "a", t = "aa";
		auto res = sln.minWindow(s, t);
		Assert(std::string(""), res);
	}
	{
		Solution sln;
		s = "bbaac", t = "aba";
		auto res = sln.minWindow(s, t);
		Assert(std::string("baa"), res);
	}
	
}

2023年4月版

class Solution {
public:
string minWindow(string s, string t) {
if (s.length() < t.length())
{
return “”;
}
std::unordered_map<char,int> setLess, setMore;
for (const char& ch : t)
{
setLess[ch]++;
}
int iRetIndex = -1;
int iRetLen = INT_MAX;
int iBeginIndex = 0;
string strRet;
for (int i = 0 ; i < s.length(); i++)
{
DelOrAdd(setLess, setMore, s[i]);
while (0 == setLess.size())
{
const int iLen = i - iBeginIndex + 1;
if (iLen < iRetLen)
{
iRetIndex = iBeginIndex;
iRetLen = iLen;
}
DelOrAdd(setMore, setLess, s[iBeginIndex]);
iBeginIndex++;
}

	}
	return (-1==iRetIndex)? "" : s.substr(iRetIndex,iRetLen);
}
void DelOrAdd(std::unordered_map<char, int>& del, std::unordered_map<char, int>& more, const char& ch)
{
	auto it = del.find(ch);
	if (del.end() == it)
	{
		more[ch]++;
	}
	else if (it->second > 1)
	{
		del[ch]--;
	}
	else 
	{
		del.erase(ch);
	}

}

};

擴展閱讀

視頻課程

有效學(xué)習(xí)：明確的目標(biāo) 及時的反饋 拉伸區(qū)（難度合適），可以先學(xué)簡單的課程，請移步CSDN學(xué)院，聽白銀講師（也就是鄙人）的講解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成戰(zhàn)斗了，為老板分憂，請學(xué)習(xí)C#入職培訓(xùn)、C++入職培訓(xùn)等課程
https://edu.csdn.net/lecturer/6176

相關(guān)下載

想高屋建瓴的學(xué)習(xí)算法，請下載《喜缺全書算法冊》doc版
https://download.csdn.net/download/he_zhidan/88348653

測試環(huán)境

操作系統(tǒng)：win7 開發(fā)環(huán)境： VS2019 C++17
或者 操作系統(tǒng)：win10 開發(fā)環(huán)境： VS2022 C++17
如無特殊說明，本算法用C++ 實現(xiàn)。

文章來源地址http://www.zghlxwxcb.cn/news/detail-772794.html

到了這里，關(guān)于【滑動窗口】【map】LeetCode:76最小覆蓋子串的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！