要划分尽可能多的区间，且相同字符只能出现在同一个区间里。采用双指针加贪心算法： 1、用flag数组记录每个字符最后出现的位置 2、对字符串遍历判断当前是否为结束节点，存储到列表res
class Solution { public List<Integer> partitionLabels(String S) { int []flag = new int[26]; int l = S.length(); //记录每个字符最后出现的位置 for(int i = 0;i < l;i++){ flag[S.charAt(i) - 'a'] = i; } List<Integer> res = new ArrayList<>(); int end = 0,start = 0; for(int i = 0;i < l;i++){ //记录当前区间的字符结束的最大end end = Math.max(end,flag[S.charAt(i) - 'a']); if(end == i){//当前节点时结束节点可以进行分区 res.add(end - start + 1); start = end + 1; } } return res; } }