思路分析:

  1. 使用unordered_map记录每个字符在字符串中最后出现的位置,以便后续快速查找。
  2. 初始化指针end和start,分别表示当前分段的结束位置和起始位置。
  3. 遍历字符串,更新end的值,保证它始终表示当前分段的最远结束位置。
  4. 当遍历到当前分段的结束位置时,计算当前分段的长度,并将其加入结果向量,然后更新下一个分段的起始位置。
  5. 最终返回存储分段长度的结果向量。
class Solution {public:// 定义成员函数partitionLabels,接受一个字符串s,返回一个整数向量vector partitionLabels(string s) {// 获取字符串长度int n = s.size();// 使用unordered_map存储每个字符在字符串中最后出现的位置unordered_map M;for (int i = 0; i < n; i++)M[s[i]] = i;// 初始化指针end和start,用于标记当前分段的结束位置和起始位置int end = 0, start = 0;// 用于存储分段长度的结果向量vector result;// 遍历字符串for (int i = 0; i < n; i++) {// 更新当前分段的结束位置end = max(end, M[s[i]]);// 如果当前遍历到的位置等于当前分段的结束位置if (i == end) {// 计算当前分段的长度,并将其加入结果向量result.push_back(end - start + 1);// 更新下一个分段的起始位置start = i + 1;}}// 返回结果向量return result;}};