LeetCode-Go 题解精讲：第 30 题 Substring with Concatenation of All Words 的滑动窗口与计数映射实现

LeetCode-Go 题解精讲：第 30 题 Substring with Concatenation of All Words 的滑动窗口与计数映射实现

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

导读

本文围绕 LeetCode 第 30 题Substring with Concatenation of All Words（串联所有单词的子串），以 leetcode/0030.Substring-with-Concatenation-of-All-Words/README.md 为骨架，深入讲解 LeetCode-Go 仓库中该题的官方 Go 解法。你将掌握：如何利用「单词定长 + 必须连续拼接」两个限定条件把看似复杂的全排列匹配问题简化为哈希计数 + 定长窗口扫描，并理解findSubstring、checkWords、copyMap三个函数的实际调用关系与边界处理，最终可以独立完成此类字符串匹配题并跑通仓库自带的单元测试。

一、题目原文与示例

You are given a string,s, and a list of words,words, that are all of the same length. Find all starting indices of substring(s) insthat is a concatenation of each word inwordsexactly once and without any intervening characters.

即：给定一个源字符串s和一个单词数组words（数组中所有单词长度相同），找出s中所有「恰好由words中每个单词各出现一次、且单词之间无任何间隔字符连续拼接而成」的子串的起始下标。

Example 1：

Input: s = "barfoothefoobarman", words = ["foo","bar"] Output: [0,9] Explanation: Substrings starting at index 0 and 9 are "barfoor" and "foobar" respectively. The output order does not matter, returning [9,0] is fine too.

Example 2：

Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"] Output: []

Example 2 值得特别留意：words中存在重复单词"word"两次，意味着目标子串中"word"也必须恰好出现两次，而源字符串中"word"只出现一次，因此结果为空。这印证了「每个单词各出现一次（含重复计数）」这一约束在实现中必须通过计数而非去重集合来落实。

二、题目大意

给定一个源字符串s，再给一个字符串数组，要求在源字符串中找到由字符串数组各种组合组成的连续串的起始下标，如果存在多个，在结果中都需要输出。

三、解题思路：两个关键限定条件

这一题看似很难，但是有 2 个限定条件也导致这题不是特别难：

1. 字符串数组里面的字符串长度都是一样的——这使我们可以把源字符串按固定长度length切成等宽的"单词块"来匹配，而不是做任意长度的子串穷举；
2. 要求字符串数组中的字符串都要连续连在一起的，前后顺序可以是任意排列组合——这意味着我们不需要枚举全排列，只需要验证「一段连续区域内，每个单词的出现次数恰好等于words中的要求次数」即可。

基于此，原文档给出的核心思路是：先将字符串数组里面的所有字符串都存到map中，并累计出现的次数；然后从源字符串头开始扫描，每次判断字符串数组里面的字符串是否全部都用完了（计数是否为 0）；如果全部都用完了，并且长度正好是字符串数组任意排列组合的总长度，就记录下这个组合的起始下标；如果不符合，就继续考察源字符串的下一个字符，直到扫完整个源字符串。

四、Go 源码实现与逐段精解

仓库中的实现位于 leetcode/0030.Substring-with-Concatenation-of-All-Words/30. Substring with Concatenation of All Words.go，完整代码如下：

package leetcode func findSubstring(s string, words []string) []int { if len(words) == 0 { return []int{} } res := []int{} counter := map[string]int{} for _, w := range words { counter[w]++ } length, totalLen, tmpCounter := len(words[0]), len(words[0])*len(words), copyMap(counter) for i, start := 0, 0; i < len(s)-length+1 && start < len(s)-length+1; i++ { //fmt.Printf("sub = %v i = %v lenght = %v start = %v tmpCounter = %v totalLen = %v\n", s[i:i+length], i, length, start, tmpCounter, totalLen) if tmpCounter[s[i:i+length]] > 0 { tmpCounter[s[i:i+length]]-- //fmt.Printf("******sub = %v i = %v lenght = %v start = %v tmpCounter = %v totalLen = %v\n", s[i:i+length], i, length, start, tmpCounter, totalLen) if checkWords(tmpCounter) && (i+length-start == totalLen) { res = append(res, start) continue } i = i + length - 1 } else { start++ i = start - 1 tmpCounter = copyMap(counter) } } return res } func checkWords(s map[string]int) bool { flag := true for _, v := range s { if v > 0 { flag = false break } } return flag } func copyMap(s map[string]int) map[string]int { c := map[string]int{} for k, v := range s { c[k] = v } return c }

4.1 三个函数的分工

• findSubstring(s string, words []string) []int：主函数。空words直接返回空切片（对应测试用例{"n", []string{}}）；否则构建需求计数表并执行滑动扫描。
• checkWords(s map[string]int) bool：判断计数表中是否所有键的计数都已经降到 0。只有全部为 0，才说明当前窗口恰好用完了每个单词。
• copyMap(s map[string]int) map[string]int：深拷贝计数表。因为每次从新起点start重新匹配时都要把计数表恢复为原始需求值，直接复用同一个 map 会因递减操作污染数据，因此必须拷贝。

4.2 关键状态变量

4.3 主循环逻辑拆解

外层循环的条件是i < len(s)-length+1 && start < len(s)-length+1，保证取子串s[i:i+length]不越界。循环体内分两种分支：

分支一：当前单词块命中需求（tmpCounter[s[i:i+length]] > 0）

说明s[i:i+length]属于需要的单词，执行：

tmpCounter[s[i:i+length]]-- if checkWords(tmpCounter) && (i+length-start == totalLen) { res = append(res, start) continue } i = i + length - 1

• 先递减对应计数；
• 若checkWords(tmpCounter)为真（所有单词都用完）且i+length-start == totalLen（窗口总长恰好等于totalLen），则start就是一个合法起始下标，记录后continue；
• 否则i = i + length - 1，配合循环末尾的i++实现一次前进length个字节——即从当前窗口直接跳到下一个单词块，这正是利用"定长单词"这一限定条件的核心优化。

分支二：当前单词块不命中需求（tmpCounter[s[i:i+length]] > 0为假）

说明从当前start出发的窗口已经不可能成立，必须换起点：

start++ i = start - 1 tmpCounter = copyMap(counter)

• 起点右移一位；
• i回到start-1，配合i++让下一次循环从新起点重新开始扫描；
• 计数表重置为原始需求（深拷贝），重新开始统计。

4.4 为什么需要双重条件判断

checkWords(tmpCounter)负责"单词全部用完"，i+length-start == totalLen负责"窗口长度达标"。二者缺一不可：前者保证每个单词恰好出现一次（计数降到 0），后者保证窗口没有越界拼接、没有把多余字符算进来。只有两者同时满足，才把start记入结果。

五、测试用例与运行验证

仓库为该题提供了 11 组测试用例，位于 leetcode/0030.Substring-with-Concatenation-of-All-Words/30. Substring with Concatenation of All Words_test.go，覆盖了常规匹配、重复单词、单单词、边界与失败场景：

测试驱动方式为表驱动测试：para30结构体承载输入（one为源字符串、two为单词数组），ans30承载期望答案，Test_Problem30遍历所有用例并打印输入输出对照。这符合仓库统一的题解测试风格。

在仓库根目录执行项目自带的测试脚本 gotest.sh（内部运行go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...），或直接对单目录执行：

go test -v ./leetcode/0030.Substring-with-Concatenation-of-All-Words/

即可看到该用例被逐一验证通过。仓库go.mod声明的 Go 版本为 1.19，测试时请使用兼容的 Go 工具链。

六、复杂度分析与延伸思考

• 时间复杂度：主循环在最坏情况下对s的每个起始位置重新扫描，每次扫描约消耗len(words)个单词块，总代价近似O(len(s) × len(words))；checkWords每次遍历计数表（键的数量不超过words去重后的个数）。相比对words做全排列（O(k!)级别）的朴素思路，本解法的哈希计数方案是质变的优化。
• 空间复杂度：counter与tmpCounter存储去重后的单词计数，空间为O(去重单词数)，另有结果切片res的开销。

可以推断，本实现还有进一步优化的空间（例如引入单词长度length的模分组、复用滑动窗口而不是每次回退start重新扫描），这也是滑动窗口类题目的常见进阶方向，例如仓库中 0076.Minimum-Window-Substring、0438.Find-All-Anagrams-in-a-String 等题目使用的都是同一类"计数 + 窗口"思想，读者可以横向对比加深理解。

七、小结

本题是"定长单词 + 连续拼接"约束下的典型字符串匹配题。核心套路可总结为三步：

1. 用map[string]int统计words中每个单词的需求次数；
2. 从源字符串逐位（或逐块）扫描，命中需求则递减计数并前进一个单词长度，不命中则移动起点并重置计数；
3. 当剩余计数全部归零且窗口长度恰为totalLen时记录起点。

掌握这一套路后，凡是"由若干定长子串任意排列组成的匹配"类问题，都可以用同样的哈希计数框架快速求解。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go