ARST打卡第238周[238/521]

发表于 2023-11-25 更新于 2023-11-26 分类于 ARST 阅读次数：

lc828_统计子串中的唯一字符【TED演讲】16岁语言天才分享：我是如何掌握20多门外语的？为什么说黑底白字界面主题配色是最垃圾的、最不该用的？推荐阅读_现代C++语言核心特性解析

Algorithm

lc828_统计子串中的唯一字符

思路:
暴力做法是双层遍历字串，然后hash映射统计只出现一次的字符.
O(n^3), 不行。

优化:
在第二重遍历的时候就直接hash记录。
O(n^2), 还是不行。

怎么重复利用呢? 看数据范围 1e5 需要保证时间复杂度在 O(nlogn), 暂时想不到好办法。

看看题解

其中计算一个字符的贡献太精巧了！只能说这个 hard 主要难在思路和那个鬼斧神工的前后插入。

class Solution {
public:
    int uniqueLetterString(string s) {
        unordered_map<char, vector<int>> index;
        for (int i = 0; i < s.size(); i++) {
            index[s[i]].emplace_back(i);
        }
        int res = 0;
        for (auto &&[_, arr]: index) {
            arr.insert(arr.begin(), -1);
            arr.emplace_back(s.size());
            for (int i = 1; i < arr.size() - 1; i++) {
                res += (arr[i] - arr[i - 1]) * (arr[i + 1] - arr[i]);
            }
        }
        return res;
    }
};