2021-01-05 | 830. 较大分组的位置

ゝ一纸荒年。 2023-01-02 12:25 95阅读 0赞

### 1. 题目描述 ###

在一个由小写字母构成的字符串 s 中，包含由一些连续的相同字符所构成的分组。

例如，在字符串 `s = "abbxxxxzyy"` 中，就含有 `"a"`, `"bb"`, `"xxxx"`, `"z"` 和 `"yy"` 这样的一些分组。

分组可以用区间 `[start, end]` 表示，其中 `start` 和 `end` 分别表示该分组的起始和终止位置的下标。上例中的 “xxxx” 分组用区间表示为 \[3,6\] 。

我们称所有包含大于或等于三个连续字符的分组为 较大分组 。

找到每一个 较大分组 的区间，按起始位置下标递增顺序排序后，返回结果。

示例 1：

输入：s = "abbxxxxzzy"
    输出：[[3,6]]
    解释："xxxx" 是一个起始于 3 且终止于 6 的较大分组。

示例 2：

输入：s = "abc"
    输出：[]
    解释："a","b" 和 "c" 均不是符合要求的较大分组。

示例 3：

输入：s = "abcdddeeeeaabbbcd"
    输出：[[3,5],[6,9],[12,14]]
    解释：较大分组为 "ddd", "eeee" 和 "bbb"

示例 4：

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

提示：

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

### 2. 解题思路 ###

**（1）直接遍历**  
对于这道题目，可以直接一趟进行遍历。初始化一个num，用来保存当前分组的长度。每次增加一个相同字符，num就加一。如果下一个字符和当前字符不同，或者是已经遍历到字符串尾部，就说明相同的字符已经遍历完了。如果此时num满足较大分组的条件，就其加入到结果中。

**复杂度分析：**

*  **时间复杂度**：O(n)，其中 n 是字符串的长度，只需要遍历一次该数组。
 *  **空间复杂度**：O(1)，只需要常数的空间来保存若干变量，返回值不计入空间复杂度。

**（2）双指针**  
除了直接遍历之外，我们还可以使用双指针来实现这个题目。

*  初始化两个指针 left 和 right 分比为0和1
 *  只要 left 和 right 值相等，就向右移动 right 指针
 *  如果 left 和 right 值不相等，就计算前面的相同字符的个数，判断个数是否大于等于3：当满足条件时，将对应的起始索引位置添加到结果列表中，维护更新 left = right；否则，直接更新 left = right。

**复杂度分析：**

### 3. 代码实现 ###

**（1）直接遍历**

/** * @param {string} s * @return {number[][]} */
    var largeGroupPositions = function(s) { 
        let res = [], num = 1, len = s.length
        
        for(let i = 0; i <= len; i++){ 
            if(i === len - 1 || s[i] !== s[i + 1]){ 
                if(num >= 3){ 
                    res.push([i - num + 1, i])
                }
                num = 1
            }else{ 
                num++
            }
        }
        return res
    };

**（2）双指针**

/** * @param {string} s * @return {number[][]} */
    var largeGroupPositions = function(s) { 
        let res = [], len = s.length, left = 0, right = 1
        
        while(right <= len){ 
            if(right === len || s[left] !== s[right]){ 
                if(right - left >= 3){ 
                    res.push([left, right - 1])
                }
                left = right
            }
            right += 1
        }
        return res
    };

### 4. 提交结果 ###

**（1）直接遍历**  
![在这里插入图片描述][20210105215059500.png]

**（2）双指针**  
![在这里插入图片描述][20210105215051926.png]

[20210105215059500.png]: /images/20221119/c9d0ee215ef14a90a6cb17d230ea7cac.png?
[20210105215051926.png]: /images/20221119/44075f2b0462441b9e7108f10b1affda.png