企业官网建设流程全解析

LeetCode 830 Positions of Large Groups 题解：Go 滑动窗口一次遍历求解较大分组区间

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

导读

本文围绕 LeetCode 第 830 题「Positions of Large Groups（较大分组的位置）」展开，基于开源仓库 LeetCode-Go 中该题的 题解文档 与其 Go 实现源码 进行讲解。这是一道典型的字符串「连续相同字符分组」问题，考察对双指针与滑动窗口思想的应用。读完本文，你将掌握如何在一次线性扫描内找出字符串中所有长度不小于 3 的连续字符分组的起止区间，理解其时间与空间复杂度，并能直接运行仓库中的测试用例进行验证。

题目背景与问题定义

在一个由小写字母构成的字符串s中，连续的相同字符会构成一个个分组（group）。例如字符串s = "abbxxxxzyy"中，依次存在分组"a"、"bb"、"xxxx"、"z"、"yy"。

每个分组可以用一个闭区间[start, end]表示，其中start与end分别是该分组在原字符串中的起始下标与终止下标（含端点）。上例中的分组"xxxx"覆盖下标3到6，即区间[3, 6]。

当一个分组的字符数量大于或等于 3时，它被定义为较大分组（large group）。题目要求返回字符串中所有较大分组的区间，并且结果必须按起始下标递增排序。

官方示例

示例 1

Input: s = "abbxxxxzzy" Output: [[3,6]] Explanation: "xxxx" is the only large group with start index 3 and end index 6.

示例 2

Input: s = "abc" Output: [] Explanation: We have groups "a", "b", and "c", none of which are large groups.

示例 3

Input: s = "abcdddeeeeaabbbcd" Output: [[3,5],[6,9],[12,14]] Explanation: The large groups are "ddd", "eeee", and "bbb".

示例 4

Input: s = "aba" Output: []

数据约束

• 1 <= s.length <= 1000
• s仅包含小写英文字母

约束决定了实现可以非常轻量：字符串最长 1000 个字符，即使采用暴力枚举所有子串也能在时限内通过，但更优雅的做法是一次线性扫描，即仓库题解采用的滑动窗口思路。

思路分析：双指针与滑动窗口

原文档的 解题思路 给出了清晰的算法骨架：

1. 利用滑动窗口的思想，先扩大窗口的右边界，找到能到达的相同字母的最右边；
2. 记录左右边界，判断该分组是否满足「长度 ≥ 3」；
3. 将窗口的左边界移动到上一次右边界的下一位置，重复上述过程，直至扫完整个字符串。

这个过程的本质是双指针扫描：用一个end指针负责向前推进并统计连续相同字符，用一个start指针记录当前分组的起点。由于字符串从左到右被一次性扫完，且end指针只会单调递增，每个字符恰好被访问一次，因此天然满足题目「按起始下标递增排序」的输出要求——扫描顺序就是下标的递增顺序，无需额外排序。

该思路在代码层面可以抽象为一个不变量：每次外层循环开始时，end都指向一个新的、尚未被归入任何分组的字符，start = end即当前分组的起点。内层循环让end一直向右移动，直到字符发生变化或越界，此时区间[start, end-1]就是完整的一个分组。

源码实现与逐行解读

仓库中该题的 Go 实现位于 830. Positions of Large Groups.go，核心函数largeGroupPositions如下：

package leetcode func largeGroupPositions(S string) [][]int { res, end := [][]int{}, 0 for end < len(S) { start, str := end, S[end] for end < len(S) && S[end] == str { end++ } if end-start >= 3 { res = append(res, []int{start, end - 1}) } } return res }

逐行解读如下：

从源码结构可以看出，该实现没有引入任何额外数据结构，仅依赖两个下标与一个结果切片，代码简洁且可读性高，非常适合作为「一次遍历统计连续段」的入门模板。

复杂度与正确性分析

时间复杂度：O(n)

内层循环中的end指针只会单调右移，永远不会回退，外层循环本身不消耗额外遍历。因此整个字符串s中的每个字符最多被end访问一次，总体时间复杂度为 O(n)，其中 n 为s.length（本题约束 n ≤ 1000）。

空间复杂度：O(1)（不含输出）

除结果切片res外，算法只使用start、end、str等常数个变量。若计入返回结果本身，最坏情况（如"aaaabbbb"这类连续多个长度为 4 的分组）结果规模为 O(n)。

正确性要点：

• 分组完备性：外层循环每次进入都从「未归类的第一个字符」开始，内层循环把连续相同字符一次性全部纳入，因此每个字符恰好属于一个分组，不重不漏；
• 区间计算：左闭右开长度end - start与闭区间[start, end-1]严格对应，长度判定与输出下标均正确；
• 结果有序：扫描自左向右进行，start单调递增，返回结果天然满足题目要求的「按起始下标递增排序」，无需额外sort。

边界情况与示例推演

边界情况

• 单个字符：s = "a"，分组"a"长度 1 < 3，返回[]；
• 恰好 3 个字符：s = "aaa"，返回[[0,2]]——长度判定使用>=而非>，3 个字符的分组必须被纳入；
• 恰好 2 个字符：s = "aa"，返回[]；
• 分组位于字符串末尾：s = "abbb"，内层循环以end == len(S)退出，此时end - 1仍为合法下标，返回[[1,3]]；
• 全串为同一字符：s = "aaaaa"，返回[[0,4]]，整个字符串就是唯一分组。

结合官方示例推演

以s = "abcdddeeeeaabbbcd"（示例 3）为例：

最终结果[[3,5],[6,9],[12,14]]与官方输出完全一致。

仓库中的测试用例与运行方式

仓库为该题提供了完整的测试文件 830. Positions of Large Groups_test.go，其中以结构体question830组织「参数-期望答案」的用例表，覆盖了官方给出的全部四个示例：

• "abbxxxxzzy"→[[3,6]]
• "abc"→ 空结果（测试中以[][]int{{}}表示空切片占位）
• "abcdddeeeeaabbbcd"→[[3,5],[6,9],[12,14]]
• "aba"→ 空结果

需要说明的是，仓库中该题的测试采用打印输出的方式验证结果（fmt.Printf输出输入与函数返回），并未使用t.Errorf断言，这与仓库部分题解测试的「演示型」风格一致；读者可对照打印结果人工核对，或自行补充断言。

在本仓库根目录（模块名见 go.mod，为github.com/halfrost/LeetCode-Go，Go 版本要求 1.19+）下，可通过以下命令运行该题测试：

# 仅运行本题测试 go test ./leetcode/0830.Positions-of-Large-Groups/ # 运行全部 LeetCode 题解测试 go test ./leetcode/...

仓库还提供了覆盖率生成脚本 gotest.sh，一条命令即可产出全量覆盖率报告：

./gotest.sh # 等价于 go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...

生成的coverage.txt位于仓库根目录，可配合 Codecov 等工具查看全仓库题解的覆盖率统计。

小结

LeetCode 830「Positions of Large Groups」是一道难度为 Easy 的字符串扫描题，但其背后蕴含的双指针/滑动窗口思想在「连续段统计」「区间合并」「字符串分组」等场景中应用广泛。LeetCode-Go 仓库中 largeGroupPositions 的实现以 O(n) 时间、O(1) 额外空间完成了任务：

• 以end指针线性推进，start记录分组起点；
• 用左闭右开长度end - start判断「长度 ≥ 3」；
• 输出闭区间[start, end-1]，天然有序。

掌握这一「一次遍历 + 连续段判定」的模式，可以迁移到 LeetCode 434（字符串中的段数）、763（划分字母区间）等同类问题上，是刷题与面试中的高频基本功。

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