题目：字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。
示例 1： 输入：S = “ababcbacadefegdehijhklij” 输出：[9,7,8]
解释：划分结果为 “ababcbaca”, “defegde”, “hijhklij”。每个字母最多出现在一个片段中。像 “ababcbacadefegde”, “hijhklij” 的划分是错误的，因为划分的片段数较少。
class Solution { public: vector<int> partitionLabels(string S) { vector<int>lastIdex(128,0); //遍历字符串，建立哈希表，存入每个字符最后一次出现的下标 for(int i = 0; i < S.size(); i++) { lastIdex[S[i]] = i; } int start = 0; int end = 0; vector<int> ans;//存放结果 //for循环再次遍历字符串 for(int i = 0; i < S.size(); i++) { //遍历的字符串中，取此字符最后一次出现的最后位置 end = max(end, lastIdex[S[i]]); //遍历直至当前位置与最后位置相等了，切割当前的字符串 if(end == i) { //将当前字符串长度存入结果中 ans.push_back(end - start + 1); //其实位置进行更新 start = end + 1; } } return ans; } };时间复杂度O(N)（两个for循环都是O(N)），空间复杂度O(N)
[[C++]Leetcode超高效刷题顺序及题目详解笔记（持续更新中）]
