專欄：50多種數(shù)據(jù)結(jié)構(gòu)徹底征服
專欄：50多種經(jīng)典圖論算法全部掌握
據(jù)環(huán)球網(wǎng)昨日報道，胡某本是一名在校大學生，最近他利用所學技術(shù)非法入侵了學校某系統(tǒng)并獲取兩萬余條該校學生個人信息。
為尋求刺激、炫耀技術(shù)，胡某通過之前發(fā)現(xiàn)的某小程序存在的技術(shù)漏洞，利用AI編寫程序，把其中盜取的上千余名學生的手機號碼在該小程序上批量注冊賬戶，后將短信驗證碼篡改為淫穢內(nèi)容發(fā)送至學生本人，對其進行短信騷擾。
這家伙也是沒底線，有這技術(shù)干啥不好，非要干一些非法的事，如果只是單純的發(fā)一些驗證碼估計也沒那么嚴重，非要把驗證碼改成淫穢內(nèi)容發(fā)送到學生手機上，這簡直就是變態(tài)。
--------------下面是今天的算法題--------------
來看下今天的算法題，這題是LeetCode的第1358題：包含所有三種字符的子字符串數(shù)目，難度是中等。
給你一個字符串 s ，它只包含三種字符 a, b 和 c 。請你返回 a，b 和 c 都 至少 出現(xiàn)過一次的子字符串數(shù)目。
示例1：
輸入：s = "abcabc" 輸出：10 解釋：包含 a，b 和 c 各至少一次的子字符串為 "abc", "abca", "abcab", "abcabc", "bca", "bcab", "bcabc", "cab", "cabc" 和 "abc" (相同字符串算多次)。
示例2：
輸入：s = "aaacb" 輸出：3 解釋：包含 a，b 和 c 各至少一次的子字符串為 "aaacb", "aacb" 和 "acb" 。
3 <= s.length <= 5 x 10^4
s 只包含字符 a，b 和 c 。
問題分析
這題說的是包含 3 種字符的子串數(shù)量，我們可以使用滑動窗口來解決。當窗口不包含 3 種字符的時候，要一直移動窗口的右邊界，直到窗口中包含 3 種字符為止。
當窗口包含 3 種字符的時候，說明這個窗口是滿足條件的子串，然后窗口中的字符和窗口右邊的字符構(gòu)成的子串也是滿足條件的，這個不要遺漏，所以總共有 n-right 個，n 是字符串的長度，right 是窗口的右邊界，由于字符串的下標是從 0 開始的，所以這里不需要在加 1 。
然后移動窗口的左邊界，如果窗口還包含 3 種字符，說明窗口還是滿足條件的，然后繼續(xù)累加子串個數(shù)……
我們舉個例子，比如字符串“acabcc”，當窗口“acab”滿足條件的時候，“acab”和右邊的“cc”都可以構(gòu)成滿足條件的子串，總共有 3 個。
縮小窗口為“cab”也是滿足條件的，它和右邊的“cc”也可以構(gòu)成滿足條件的子串，又有 3 個。
繼續(xù)滑動窗口為“abc”也是滿足條件的，它和最后一個字符 “c” 也可以構(gòu)成滿足條件的子串，又有 2 個。
所以總共有 8 個，分別是[acab,acabc,acabcc,cab,cabc,cabcc,abc,abcc]。
JAVA：
public int numberOfSubstrings(String s) { int[] mp = newint[128]; int left = 0, right = 0, n = s.length(); int cnt = 0;// 新的字符個數(shù) int ans = 0;// 返回的結(jié)果 while (right < n) { if (mp[s.charAt(right)]++ == 0)// 遇到新的字符 cnt++; while (cnt == 3) { if (--mp[s.charAt(left++)] == 0) cnt--;// 移除一個新字符 ans += n - right; } right++; } return ans; }C++：
public: int numberOfSubstrings(string s) { vector
mp(128, 0); int left = 0, right = 0, n = s.length(); int cnt = 0;// 新的字符個數(shù) int ans = 0;// 返回的結(jié)果 while (right < n) { if (mp[s[right]]++ == 0)// 遇到新的字符 cnt++; while (cnt == 3) { if (--mp[s[left++]] == 0) cnt--;// 移除一個新字符 ans += n - right; } right++; } return ans; }
筆者簡介
博哥，真名：王一博，畢業(yè)十多年， 作者，專注于 數(shù)據(jù)結(jié)構(gòu)和算法 的講解，在全球30多個算法網(wǎng)站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關(guān)注，也可以 下載我整理的1000多頁的PDF算法文檔 。
熱門跟貼