LeetCode#763

LeetCode#763划分字母区间

题目链接
先说我的解法吧，使用一个可以把字符类型和布尔类型对应上的stl储存这段中是否已经遇到了当前这个字符，如果遇到了则直接跳过找继续遍历字符串（因为第一次找的时候记录的就是这个字符的最后一次出现的位置），如果遍历到当前字符串的最长距离（也就是当前这个串中，所有的出现过的字符中的最后一个）也就是找到了当前的这个字符串。

class Solution {
public:
    vector<int> partitionLabels(string S) {
        unordered_map<char,bool>hash;
        vector<int>ans;
        int longest = 0;
        int start = 0;
        for(int i = 0 ; i < S.size() ; i++)
        {
            if(hash[S[i]] == false)
            {
                hash[S[i]] == true;
                for(int j = S.size() - 1 ; j >longest ; j--)
                {
                    if(S[j] == S[i])
                        longest = j;
                }
            }
            if(i == longest)
            {
                //cout << longest << " " << start << endl;
                ans.push_back(longest-start+1);
                longest++;
                start=longest;
                hash.clear();
            }
        }
        return ans;
    }
};

我的思路和题解思路差不多(假装，但是不管是开一个哈希表还是一个map都需要开辟额外的空间，题解直接用了双指针的方式降低了空间复杂度（当然直接访问数组的时间复杂度肯定也比哈希表快），附代码：

class Solution {
public:
    vector<int> partitionLabels(string S) {
        int last[26];
        int length = S.size();
        for (int i = 0; i < length; i++) {
            last[S[i] - 'a'] = i;
        }
        vector<int> partition;
        int start = 0, end = 0;
        for (int i = 0; i < length; i++) {
            end = max(end, last[S[i] - 'a']);
            if (i == end) {
                partition.push_back(end - start + 1);
                start = end + 1;
            }
        }
        return partition;
    }
};