【LeetCode 热题 100】滑动窗口最大值 / 最小覆盖子串 / 轮转数组 / 缺失的第一个正数

子串

和为 K 的子数组

• 和为 K 的子数组

代码语言：javascript代码运行次数：0运行复制

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> hash;
        hash[0] = 1;
        int pre = 0, res = 0;
        for (auto e : nums)
        {
            pre += e;
            res += hash[pre - k];
            hash[pre]++;
        }
        return res;
    }
};

---

滑动窗口最大值

• 滑动窗口最大值

看完这个题很容易想到用优先级队列，但是我写了一半突然意识到，当左侧出窗口时优先级队列好像无法立马找到这个值并删除，所以就放弃了这个想法； 于是就又想到set也能排序，通过 rbegin() 返回最大值对应的迭代器，但是数组中可能会出现重复的数，而set会去重，所以就又想到 multiset，它可以真正意义上的排序。 但是测试了一下发现AC不了，又想到 multiset 虽然不去重，但是 erase 会把所有相同的值都删除，所以这个办法好像又不行； 但是又突然想到之前学习 multiset 的时候测试过不同的 erase 删除，发现传值、传迭代器、传迭代器区间，最后的结果是不同的。其中传值和传迭代器区间会把所有相同的值都删除，而传迭代器的话只会删除一个。 于是又测试了一下，终于过了。但是N*logN的时间负责度居然才击败了百分之5的用户

发布者：admin，转转请注明出处：http://www.yc00.com/web/1747520752a4647456.html