千问 LeetCode 2949. 统计美丽子字符串 II Go实现

这道题用 Go 来实现不仅代码会更简洁运行效率也会非常高。核心思路依然是“前缀和 哈希表”我们只需要把 Java 的逻辑平滑地转换成 Go 的语法习惯即可。核心思路回顾1. 数学转化子字符串要美丽元音和辅音数量必须相等各占一半设长度为 L则各为 L/2。且 (L/2 * L/2) % k 0。我们需要算出满足这个条件的最小子字符串长度周期 mod。2. 前缀和 哈希表遍历时元音记为 1辅音记为 -1。如果两个位置的前缀和相等且它们的下标差是 mod 的倍数那么这段子字符串就是“美丽”的。我们用哈希表记录 (前缀和, 下标%mod) 出现的次数。Go 代码实现func beautifulSubstrings(s string, k int) int64 {// 1. 计算满足 (L/2)^2 % k 0 的最小周期长度 modmod : getMod(k)var ans int64 0sum : 0 // 前缀和元音1辅音-1// 2. 哈希表记录状态 (前缀和, 下标 % mod) 出现的次数// Go 中可以用 map[[2]int]int 或者 map[string]int 作为复合键// 这里使用 [2]int 数组作为 key性能更好且更符合 Go 习惯mapState : make(map[[2]int]int)// 初始状态前缀和为0虚拟下标为 -1。// (-1) % mod 在 Go 中结果为负数需要处理为 mod - 1mapState[[2]int{mod - 1, 0}] 1for i : 0; i len(s); i {c : s[i]// 遇到元音1辅音-1if c a || c e || c i || c o || c u {sum} else {sum--}// 当前状态的下标余数remainder : i % modkey : [2]int{remainder, sum}// 如果之前出现过相同的状态说明中间这段子字符串满足条件ans int64(mapState[key])// 更新当前状态的出现次数mapState[key]}return ans}// 对 4*k 进行质因数分解求出满足 x^2 % (4*k) 0 的最小 xfunc getMod(k int) int {m : 4 * kmod : 1for i : 2; i*i m; i {if m%i 0 {cnt : 0for m%i 0 {m / icnt}// 如果质因数的次数是奇数需要多乘一个 i 保证平方后能被整除// (cnt 1) / 2 等价于向上取整 cnt / 2power : (cnt 1) / 2for j : 0; j power; j {mod * i}}}// 处理剩下的最大质因数if m 1 {mod * m}return mod}Go 实现的细节亮点1. 复合键的使用在 Java 中我们通常把两个数拼成字符串 remainder , sum 当作 Key。而在 Go 中我们可以直接使用固定长度的数组 [2]int{remainder, sum} 作为 Map 的键不仅写起来清爽底层的哈希计算效率也更高。2. 负数取模处理Go 语言中-1 % 5 的结果是 -1而在 Java/Python 中可能是 4。所以我们在初始化哈希表时需要手动将虚拟下标 -1 的余数处理为 mod - 1。3. 类型转换题目要求返回 int64在累加结果时记得把 map 中取出的 int 强转为 int64。复杂度分析* 时间复杂度O(n sqrt(k))。遍历字符串 O(n)计算 mod 质因数分解 O(sqrt(k))。* 空间复杂度O(n)。哈希表最多存储 n 个状态。