LeetCode-763.划分字母区间、双指针

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。 示例 1： 输入：S = “ababcbacadefegdehijhklij” 输出：[9,7,8] 解释： 划分结果为 “ababcbaca”, “defegde”, “hijhklij”。 每个字母最多出现在一个片段中。 像 “ababcbacadefegde”, “hijhklij” 的划分是错误的，因为划分的片段数较少。 来源：力扣（LeetCode）

题目分析

①．划分的每个区间中的所有元素的最远位置包含在区间内即可。 ②．使用 unordered_map 提前记录每个字符的最远位置，使用时可直接获取 ③．先根据左边界元素初始化一个区间，然后遍历区间内的字符来刷新右边界，直到遍历到了右边界，即找到了一个最小区间，记录界面并开始下一个区间即可。

代码示例

class Solution { public: vector<int> partitionLabels(string S) { vector<int> res;// int size = S.size(); unordered_map<char,int> indexmap;//记录每个字符最远的位置 for( int i = 0;i < size; ++i ) { indexmap[S[i]] = i; } int left = 0;//左边界 int right = 0;//右边界 int mid = 0;//范围遍历下标 while(left < size) { if( left == right )//左右边界位于起点，此时要初始化右边界 { char c = S[left];//根据 left 找 right 初始值 right = indexmap[c];//初始化右边界 } //用 mid 在 left 到 right 范围内遍历 if( mid == right )//遍历到了右边界，本阶段结束 { res.push_back(right-left+1);//保存结果 left = right+1; right = left; mid = left; } else { // 用 mid 来刷新 right char c = S[mid]; int maxright = indexmap[c]; if( maxright > right) right = maxright;//更新 right; mid++; } } return res; } };