763. 划分字母区间

题目：https://leetcode-cn.com/problems/partition-labels/

代码：

class Solution {

    public List<Integer> partitionLabels(String S) {
        char[] chars = S.toCharArray();
        //统计a-z每个字母的开头和结尾位置
        int[][] letter = new int[26][2];
        for (int i = 0; i < 26; i++) {
            char c = (char) ('a' + i);
            letter[i][0] = S.indexOf(c);
            letter[i][1] = S.lastIndexOf(c);
        }
        //截取字符串获取结果
        List<Integer> res = new ArrayList<>();
        int start = 0;
        int end = 0;
        for (int i = 0; i < chars.length; i++) {
            char c = chars[i];
            if (letter[c - 'a'][0] > end) {
                //开启新的字符串，记录上一个字符串结果，设置新字符串start
                res.add(end - start + 1);
                start = letter[c - 'a'][0];
            }
            if (letter[c - 'a'][1] > end) {
                //设置end
                end = letter[c - 'a'][1];
            }
        }
        //记录最后一个结果
        res.add(end - start + 1);

        return res;
    }

}

定义一个二维数组，第一个维度为a-z，第二个维度记录2个值，字母c在字符串中的开头和结尾的索引值。

这样我们只需要通过一次遍历即可获得字符串S中每个字母的区间范围，接下来我们只需要对区间进行合并（有重合部分的区间合并成1个区间）

实现方法是：我们再次遍历S，这样我们对于一个区间的start就肯定是最小值，这个时候end值不确定，因为可能存在重合区间，所以end值可能会变大，需要通过继续遍历来确定end的最终值，具体实现参考代码。