【优选算法必刷100题】第015题（同向双指针：滑动窗口算法）：串联所有单词的子串

艾莉丝努力练剑

发布于 2025-11-16 20:32:40

140

文章被收录于专栏：C / C++C / C++

015 串联所有单词的子串

力扣链接：30. 串联所有单词的子串

力扣题解链接：滑动窗口 + 哈希表解决【串联所有单词的子串】

题目描述：

1.1 算法思路

1.1.1 算法思路一：暴力解法——暴力枚举 + 哈希表

如果我们把每一个单词看成一个一个字母，问题就变成了找到【字符串中所有的字母异位词】。无非就是之前处理的对象是一个一个的字符，我们这里处理的对象是一个一个的单词。

1.1.2 算法思路二 (和014几乎一样，略有区别 )：滑动窗口 + 哈希表

区别主要有以下三点：

1、哈希表：hash<string,int> ——

string是字符串，int是次数；

2、left与right指针的移动——

移动的步长是每个单词的长度；

3、滑动窗口执行的次数——

len次。

这样做的好处主要有提升以下三点能力——

1、将算法原理转换成代码；

2、容器的使用——

没有必要专门去背那些容器，通过做题来快速记忆，做一题记一个：只要这道题能通过，那这个容器你就一定能记得非常清楚。

3、细节的处理。

当然，如果对string、hash这几个容器不是很熟悉的话就不要“苦坐菩提树”了。

1.2 算法实现

1.2.1 博主的实现：C++实现

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ret;
        unordered_map<string,int> hash1;// 保存 words 里面所有单词的频次
        for(auto s : words) hash1[s]++;

        int len = words[0].size(),m = words.size();
        for(int i = 0;i < len;i++) //执行len次滑动窗口
        {
            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(hash2[in] <= hash1[in]) count++;
                // 判断
                if(right - left + 1 > len * m)
                {
                    // 出窗口 + 维护count
                    string out = s.substr(left,len);
                    //出窗口前维护一下count
                    if(hash2[out] <= hash1[out]) count--;
                    hash2[out]--;
                    //小细节：出完窗口之后left要向后移动
                    left += len;
                }
                // 更新结果
                if(count == m) ret.push_back(left);
            }
        }
        return ret;
    }
};

时间复杂度：O(n)，空间复杂度：O(1)。

C++ 运行结果：

这里有个小细节：如果hash表里面没有in这个字符串，它会重新搞一个进去，会一定程度上降低时间效率，我们这里判断一下就好了——

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ret;
        unordered_map<string,int> hash1;// 保存 words 里面所有单词的频次
        for(auto s : words) hash1[s]++;

        int len = words[0].size(),m = words.size();
        for(int i = 0;i < len;i++) //执行len次滑动窗口
        {
            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++;
                // 判断
                if(right - left + 1 > len * m)
                {
                    // 出窗口 + 维护count
                    string out = s.substr(left,len);
                    //出窗口前维护一下count
                    if(hash2.count(in) && hash2[out] <= hash1[out]) count--;
                    hash2[out]--;
                    //小细节：出完窗口之后left要向后移动
                    left += len;
                }
                // 更新结果
                if(count == m) ret.push_back(left);
            }
        }
        return ret;
    }
};

时间复杂度：O(n)，空间复杂度：O(1)。

对比一下，还是会快一点的，如果不明显，多提交几次就可以看出来了。

1.2.2 Java实现

class Solution
{
    public List<Integer> findSubstring(String s, String[] words)
    {
        List<Integer> ret = new ArrayList<Integer>();
        // 保存字典中所有单词的频次 
        Map<String, Integer> hash1 = new HashMap<String, Integer>();
        for (String str : words) hash1.put(str, hash1.getOrDefault(str, 0) + 1);
        int len = words[0].length(), m = words.length;
        for (int i = 0; i < len; i++) // 执⾏次数 
        {
            // 保存窗⼝内所有单词的频次 
            Map<String, Integer> hash2 = new HashMap<String, Integer>();
            for (int left = i, right = i, count = 0; right + len <= s.length();
                right += len)
            {
                // 进窗⼝ + 维护 count 
                String in = s.substring(right, right + len);
                hash2.put(in, hash2.getOrDefault(in, 0) + 1);
                if (hash2.get(in) <= hash1.getOrDefault(in, 0)) count++;
                // 判断 
                if (right - left + 1 > len * m)
                {
                    // 出窗⼝ + 维护 count 
                    String out = s.substring(left, left + len);
                    if (hash2.get(out) <= hash1.getOrDefault(out, 0)) count--;
                    hash2.put(out, hash2.get(out) - 1);
                    left += len;
                }
                // 更新结果 
                if (count == m) ret.add(left);
            }
        }
        return ret;
    }
};