今天來以“滑動窗口”的思想來詳解一道比較困難的題目——串聯所有單詞的子串，有需要借鑒即可。

1.題目

題目鏈接：LINK

這道題如果把每個字符串看成一個字母，就是另外一道中等難度的題目，即，找到字符串中所有字母異位詞：LINK

所以說白了，就是把每個字符串來當作一個字母進行處理，當然這僅僅是思想，相比于異位詞這個題來說，現在這道比較困難的題目還有以下不同的區別需要注意：

• ①哈希表不同
• ②left，right的起始位置，賦值不同
• ③滑動窗口的執行次數

2.下面是示例代碼

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {vector<int> ret;unordered_map<string,int> hash_w;for(int i = 0; i < words.size(); i++){string str = words[i];hash_w[str]++;}for(int i = 0; i < words[0].size(); i++){unordered_map<string,int> hash_s;for(int left = i, right = i,count = 0; right + words[0].size() <= s.size(); right+=words[0].size()){//進窗口string in = s.substr(right,words[0].size());//取子串hash_s[in]++;if(hash_w.count(in) && hash_s[in] <= hash_w[in])count++;//判斷if(right - left + 1 > words[0].size() * words.size()){//出窗口string out = s.substr(left,words[0].size());if(hash_w.count(out) && hash_s[out] <= hash_w[out])count--;//這個地方需要注意要在--之前進行判斷hash_s[out]--;left+=words[0].size();}//更新結果if(count == words.size())ret.push_back(left);}}return ret;}
};

3.總結

• 一、經驗
  這道題如果有“找到字符串中所有字母異位詞”這道題的經驗，說實在的不難，但前提是得有這個思想，沒做過“找到字符串中所有字母異位詞”這道題直接做這個的比較困難的題目的話會很難受。

• 二、再就是語法上：

  • ①是對容器的基本語法要有點了解，知道會用一些基本的接口。
  • ②是我上面這個代碼其實還做了一點點語法優化
    就是在判斷count是否++或者–時候那個條件，即：if(hash_w.count(in) && hash_s[in] <= hash_w[in])count++;如果hash_w[in]不存在他會創建一個in，有點消耗時間

---

EOF