题解 | #分品种#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return int整型一维数组
     */
     public static int[] partitionLabels (String s) {
        if(s.length()==0){
            return new int[]{};
        }
        Map<Character,Integer> map = new HashMap<>();
        LinkedList<Integer> linkedList = new LinkedList<>();
        int left = 0;
        int right = 0;
        for(int i=0;i<s.length();i++){
           map.put(s.charAt(i),i);
        }
        for(int i=0;i<s.length();i++){
            if(map.get(s.charAt(i))==i && i>=right) {
                linkedList.add(i-left+1);
                left = i+1;
                right= i+1;
            }else{
                right = Math.max(right,map.get(s.charAt(i)));
                left = Math.min(left,i);
            }
        }
        int[] arr = new int[linkedList.size()];
        for(int i=0;i<linkedList.size();i++){
            arr[i] = linkedList.get(i);
        }
        return arr;
    }
}

本题考察的知识点是贪心算法，所用编程语言是java。

我是采用双指针加哈希表来做的，我先利用哈希表将各字符的出现的最后位置存储在哈希表中。初始化左右指针都为0，然后遍历整个字符串

如果当前字符在哈希表中存储的位置就是当前位置，且当前位置不小于右指针，则需要将right-left+1的长度存储在集合当中，同时更新左指针和右指针的位置为当前位置加一

如果当前字符在哈希表中存储的位置不是当前位置，说明存在重复的字符，则需要更新右指针的位置为哈希表存储的位置和右指针位置的最大值，同时也更新左指针的位置为当前位置和左指针位置的最小值