找到字符串中所有字母异位词

怎样从“在 s="abab" 中找出所有 p="ab" 的字母异位词子串的起始下标。”推导出 滑动窗口 · 定长，并证明每次状态变化都不会漏掉答案？

中心结论：异位词长度必等于 |p|,所以用定长窗口;每右移一格进一个字符、出一个字符,再比对计数。

给定一个字符串 s 和一个非空字符串 p，找出 s 中的所有是 p 的 Anagrams 字符串的子串，返回这些子串的起始索引。Anagrams 的意思是和一个字符串的所有字符都一样，只是排列组合不同。

在本站主例中，在 s="abab" 中找出所有 p="ab" 的字母异位词子串的起始下标。

算法最终需要得到或观察：异位词起始下标为 [0,1,2]。

枚举所有子串会反复统计大量相同字符；窗口只处理右端新加入和左端刚移出的增量。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“伸缩窗口”，明确答案需要观察什么。
2. 2状态只维护 定长窗口、模式串需求计数 need、窗口计数 win。
3. 3转移每一步按照 异位词长度必等于 |p|,所以用定长窗口;每右移一格进一个字符、出一个字符,再比对计数。
4. 4收尾读取 异位词起始下标为 [0,1,2]。，并复核边界与复杂度。

右端扩张负责获得新信息，左端收缩负责恢复合法性。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：定长窗口、模式串需求计数 need、窗口计数 win。

这道题是一道考“滑动窗口”的题目。和第 3 题，第 76 题，第 567 题类似的。解法也是用 freq[256] 记录每个字符的出现的频次次数。滑动窗口左边界往右滑动的时候，划过去的元素释放次数(即次数 ++)，滑动窗口右边界往右滑动的时候，划过去的元素消耗次数(即次数 \-\-)。右边界和左边界相差 len(p) 的时候，需要判断每个元素是否都用过一遍了。具体做法是每经过一个符合规范的元素，count 就 \-\-，count 初始值是 len(p)，当每个元素都符合规范的时候，右边界和左边界相差 len(p) 的时候，count 也会等于 0 。当区间内有不符合规范的元素(freq < 0 或者是不存在的元素)，那么当区间达到 len(p) 的时候，count 无法减少到 0，区间右移动的时候，左边界又会开始 count ++，只有当左边界移出了这些不合规范的元素以后，才可能出现 count = 0 的情况，即找到 Anagrams 的情况。

异位词长度必等于 |p|,所以用定长窗口;每右移一格进一个字符、出一个字符,再比对计数。

执行过程中持续维护：定长窗口、模式串需求计数 need、窗口计数 win。

正确性依赖以下不变量：窗口宽度恒等于 |p|;窗口计数与 need 相等 ⇔ 该窗口是异位词。

面试时可以压缩为：异位词长度固定等于 |p|,所以用定长滑动窗口:维护窗口字符计数,每滑一格进出各一个字符再和 need 比对,相等则记录左边界,O(n)。

落到当前题，执行机制可以压缩为：异位词长度必等于 |p|,所以用定长窗口;每右移一格进一个字符、出一个字符,再比对计数。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入在 s="abab" 中找出所有 p="ab" 的字母异位词子串的起始下标。 因为：异位词长度必等于 |p|,所以用定长窗口;每右移一格进一个字符、出一个字符,再比对计数。
2. 2窗口装入 'c'把 'c' 计入窗口计数。 因为：窗口未满时只装入,不比较。
3. 3下标 0 是一个异位词窗口字符计数与 need 完全一致,记录左边界。 因为：定长窗口每右移一格:进一个字符、出一个字符,再做一次定长比较。
4. 4下标 1 窗口不匹配窗口字符计数与 need 不一致,滑过。 因为：定长窗口每右移一格:进一个字符、出一个字符,再做一次定长比较。
5. 5下标 3 窗口不匹配窗口字符计数与 need 不一致,滑过。 因为：定长窗口每右移一格:进一个字符、出一个字符,再做一次定长比较。
6. 6下标 5 窗口不匹配窗口字符计数与 need 不一致,滑过。 因为：定长窗口每右移一格:进一个字符、出一个字符,再做一次定长比较。
7. 7下标 7 窗口不匹配窗口字符计数与 need 不一致,滑过。 因为：定长窗口每右移一格:进一个字符、出一个字符,再做一次定长比较。
8. 8收尾与复杂度异位词起始下标为 [0,1,2]。 因为：时间 O(n) · 空间 O(1)。异位词长度必等于 |p|,所以用定长窗口;每右移一格进一个字符、出一个字符,再比对计数。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

func findAnagrams(s string, p string) []int {
	var freq [256]int
	result := []int{}
	if len(s) == 0 || len(s) < len(p) {
		return result
	}
	for i := 0; i < len(p); i++ {
		freq[p[i]-'a']++
	}
	left, right, count := 0, 0, len(p)

	for right < len(s) {
		if freq[s[right]-'a'] >= 1 {
			count--
		}
		freq[s[right]-'a']--
		right++
		if count == 0 {
			result = append(result, left)
		}
		if right-left == len(p) {
			if freq[s[left]-'a'] >= 0 {
				count++
			}
			freq[s[left]-'a']++
			left++
		}

	}
	return result
}

func main() {
    // 1. 主例
    //    输入：mode="find-anagrams", text="cbaebabacd", pattern="abc"
    //    期望：异位词起始下标为 [0,1,2]。
    //
    // 2. 失败 / 未命中
    //    检查：窗口未满时只装入不比较;比较只在窗口宽度等于 |p| 时进行。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC242 有效字母异位词；LC3 无重复字符最长子串
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意在 s="abab" 中找出所有 p="ab" 的字母异位词子串的起始下标。
2. 2重复枚举所有子串会反复统计大量相同字符；窗口只处理右端新加入和左端刚移出的增量。
3. 3优化异位词长度必等于 |p|,所以用定长窗口;每右移一格进一个字符、出一个字符,再比对计数。
4. 4证明窗口宽度恒等于 |p|;窗口计数与 need 相等 ⇔ 该窗口是异位词。
5. 5复杂度时间 O(n)，空间 O(1)