算法题 较大分组的位置

830. 较大分组的位置

问题描述

在一个由小写字母组成的字符串s中，如果某一组连续字符的长度大于或等于3，则称其为较大分组。

返回每一个较大分组的起始和结束位置（索引从 0 开始）。结果按起始位置升序排列。

示例：

输入:s="abbxxxxzzy"输出:[[3,6]]解释:"xxxx"是一个较大分组，起始位置3，结束位置6。

输入:s="abc"输出:[]解释:没有长度≥3的连续字符组。

输入:s="abcdddeeeeaabbbcd"输出:[[3,5],[6,9],[12,14]]解释:"ddd"、"eeee"、"bbb"都是较大分组。

输入:s="aba"输出:[]

算法思路

双指针：

1. 核心思想：

   • 使用两个指针标记当前连续字符组的起始和结束位置
   • 遍历字符串，当字符发生变化时，检查当前组的长度

2. 边界处理：

   • 空字符串或单字符：直接返回空列表
   • 整个字符串都是同一字符：检查总长度是否 ≥ 3

代码实现

importjava.util.*;classSolution{/** * 找出字符串中所有较大分组（连续相同字符长度≥3）的位置 * * @param s 输入字符串（仅包含小写字母） * @return 较大分组的起始和结束位置列表，按起始位置升序排列 */publicList<List<Integer>>largeGroupPositions(Strings){List<List<Integer>>result=newArrayList<>();// 边界情况：字符串长度小于3，不可能有较大分组if(s==null||s.length()<3){returnresult;}intn=s.length();intstart=0;// 当前连续字符组的起始位置// 从索引1开始遍历，比较当前字符与前一个字符for(inti=1;i<n;i++){// 当字符发生变化时，处理前一个字符组if(s.charAt(i)!=s.charAt(i-1)){// 计算当前组的长度intlength=i-start;// 如果长度≥3，添加到结果中if(length>=3){List<Integer>group=Arrays.asList(start,i-1);result.add(group);}// 更新起始位置为当前字符的位置start=i;}}// 处理最后一个字符组（字符串末尾的情况）// 最后一个组的长度为 n - startif(n-start>=3){List<Integer>group=Arrays.asList(start,n-1);result.add(group);}returnresult;}}

算法分析

• 时间复杂度：O(n)
  • 只需要遍历字符串一次
  • 每个字符只被访问一次
• 空间复杂度：O(1)（不计算输出空间）
  • 除了存储结果外，只使用常数额外空间

算法过程

输入：s = "abcdddeeeeaabbbcd"

1. 初始化：start = 0
2. i = 1：'b' != 'a'，组长度 = 1-0 = 1 < 3，start = 1
3. i = 2：'c' != 'b'，组长度 = 2-1 = 1 < 3，start = 2
4. i = 3：'d' != 'c'，组长度 = 3-2 = 1 < 3，start = 3
5. i = 4：'d' == 'd'，继续
6. i = 5：'d' == 'd'，继续
7. i = 6：'e' != 'd'，组长度 = 6-3 = 3 ≥ 3，添加[3,5]，start = 6
8. i = 7,8,9：连续'e'，继续
9. i = 10：'a' != 'e'，组长度 = 10-6 = 4 ≥ 3，添加[6,9]，start = 10
10. i = 11：'a' == 'a'，继续
11. i = 12：'b' != 'a'，组长度 = 12-10 = 2 < 3，start = 12
12. i = 13,14：连续'b'，继续
13. i = 15：'c' != 'b'，组长度 = 15-12 = 3 ≥ 3，添加[12,14]，start = 15
14. i = 16：'d' != 'c'，组长度 = 16-15 = 1 < 3，start = 16
15. 循环结束：处理末尾，组长度 = 17-16 = 1 < 3

结果：

[[3,5],[6,9],[12,14]]

测试用例

publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1：标准示例Strings1="abbxxxxzzy";System.out.println("Test 1: "+solution.largeGroupPositions(s1));// [[3,6]]// 测试用例2：无较大分组Strings2="abc";System.out.println("Test 2: "+solution.largeGroupPositions(s2));// []// 测试用例3：多个较大分组Strings3="abcdddeeeeaabbbcd";System.out.println("Test 3: "+solution.largeGroupPositions(s3));// [[3,5],[6,9],[12,14]]// 测试用例4：回文结构Strings4="aba";System.out.println("Test 4: "+solution.largeGroupPositions(s4));// []// 测试用例5：整个字符串都是同一字符Strings5="aaaaaa";System.out.println("Test 5: "+solution.largeGroupPositions(s5));// [[0,5]]// 测试用例6：空字符串Strings6="";System.out.println("Test 6: "+solution.largeGroupPositions(s6));// []// 测试用例7：单字符Strings7="a";System.out.println("Test 7: "+solution.largeGroupPositions(s7));// []// 测试用例8：两字符Strings8="aa";System.out.println("Test 8: "+solution.largeGroupPositions(s8));// []// 测试用例9：正好3个字符Strings9="aaa";System.out.println("Test 9: "+solution.largeGroupPositions(s9));// [[0,2]]// 测试用例10：结尾有较大分组Strings10="aaabbb";System.out.println("Test 10: "+solution.largeGroupPositions(s10));// [[0,2],[3,5]]// 测试用例11：开头有较大分组Strings11="bbbaaa";System.out.println("Test 11: "+solution.largeGroupPositions(s11));// [[0,2],[3,5]]}

关键点

1. 边界处理：

   • 字符串长度小于3时直接返回空列表
   • 处理字符串末尾的字符组（循环结束后）

2. 指针更新：

   • 只有在字符发生变化时才更新起始位置
   • 长度计算为i - start（当前索引减去起始索引）

常见问题

1. 为什么需要单独处理末尾的字符组？
   循环在i < n时结束，最后一个字符组不会触发字符变化的条件，需要在循环外单独处理。