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

    ⭐️个人主页：@小羊     ⭐️所属专栏：LeetCode 热题 100     很荣幸您能阅读我的文章，诚请批评指点，接待接待 ~   

  

---

子串

和为 K 的子数组

• 和为 K 的子数组
  

1. class Solution {
2. public:
3.     int subarraySum(vector<int>& nums, int k) {
4.         unordered_map<int, int> hash;
5.         hash[0] = 1;
6.         int pre = 0, res = 0;
7.         for (auto e : nums)
8.         {
9.             pre += e;
10.             res += hash[pre - k];
11.             hash[pre]++;
12.         }
13.         return res;
14.     }
15. };

复制代码

---

滑动窗口最大值

• 滑动窗口最大值
  

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