首页 > itarticle > 算法笔记: 力扣#830 较大分组的位置

算法笔记: 力扣#830 较大分组的位置

admin 11月 12, 2020 0

问题描述

解法

分析

Python 实现

class :
    def largeGroupPositions(self, S):
        """
        :type S: str
        :rtype: List[List[int]]
        """
        start = 0
        end = 0
        ans = []
        for i in range(1, len(S)):
            if S[i] == S[i-1]:
                end = i
            else:
                if end - start >= 2:
                    ans.append([start, end])
                start = i
        if end - start >= 2:
                    ans.append([start, end])
        return ans

Java 实现

class  {
    public List<List<Integer>> largeGroupPositions(String S) {
        int start = 0;
        int end = 0;
        List<List<Integer>> ans = new ArrayList();
        for(int i = 1; i < S.length(); i++){
            if(S.charAt(i-1)==S.charAt(i)){
                end = i;
            }else{
                if(end-start>=2){
                    ans.add(Arrays.asList(new Integer[]{start, end}));
                }
                start = i;
            }
        }
        if(end-start>=2){
            ans.add(Arrays.asList(new Integer[]{start, end}));
        }
        return ans;
    }
}

时间复杂度

O(n).

空间复杂度

O(n).

链接

830. Positions of Large Groups
830. 较大分组的位置
 (English version) Algorithm Notes: Leetcode#830 Positions of Large Groups