力扣精选算法100题——串联所有单词的字串(滑动窗口专题）

本题链接——串联所有单词的字串

本题和找到字符串中所有字母异位词题目非常相似，思路都是一样。通过自己的大脑能发现其中的相似之处。

第一步：了解题意

就按实例来分析吧，这样更通俗易懂。

• words=["ab","cd","ef"]，这是一个字符串数组，里面的每个字符串长度都是相等的。
• words里面的字符串串联起来的顺序有 "abcdef"，?"abefcd"，"cdabef"，?"cdefab"，"efabcd"， 和?"efcdab"?都是串联子串,但是这个不是"acdbef",因为每个字符串的"ab","cd","ef"都是固定顺序，是不能修改的。
• 比如s="abbcdefab",这里就存在串联字串"cdefab",每个字符串里面的字符顺序相同，字符串数组中各个字符串顺序可以不同，都是可以的。
• 连接的子字符串的长度必须是words字符串数组中（每个字符串长度*字符串的个数）

其中s字符串中就有存在。?

只要返回符合条件的字符串的起始索引即可。

第二步：算法原理

我们有没有发现 “找到字符串中所有字母异位词” 是找匹配的字符，字符顺序可以改变?，这一题找到字符串匹配即可，每个字符串顺序可以改变。

现在看是不是一样了，每个字符串里面的字符顺序是不能改变的，但是字符串顺序可以改变。

所以就延申了"字母异位词"思路了。

不同之处：

1.哈希表：

“找到字符串中所有字母异位词”这个题目记录的是字母的个数——用哈希表模拟数组

”串联所有单词的字串“这个题目记录的是字符串的个数——用unordered_map<string,int>表示字符串出现的次数。

2.left和right

移动的步数不再是1，而是每个字符串的长度

3.窗口的执行次数

每个字符串长度len次

这里有个小细节就是?

第三步：实现代码

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int>ret;
        unordered_map<string,int> hash1;//保存word里面的所有单词的频次
        for(auto s:words)hash1[s]++;//对每个字符串进行计数
        int len=words[0].size(),m=words.size();
        for(int i=0;i<len;i++)
        {
            unordered_map<string,int>hash2;//维护窗口内的单词频次
            for(int left=i,right=i,count=0;right+len<=s.size();right+=len)
            {
                //进窗口+维护count
                string in=s.substr(right,len);
                hash2[in]++;
                if(hash1.count(in)&&hash2[in]<=hash1[in])count++;
                //先判断in字符串是否在hash1表中存在，如果存在那么就进行下一步
                //判断
                if(right-left+1>len*m)
                {
                    //出窗口+维护count
                    string out=s.substr(left,len);
                    if(hash1.count(out)&&hash2[out]<=hash1[out])count--;
                    hash2[out]--;
                    left+=len;
                }
                //更新结果
                if(count==m) ret.push_back(left);
            }
        }
        return ret;
    }
};

是c++还是java？