qidao123.com技术社区-IT企服评测·应用市场

标题: 【LeetCode 热题 100】滑动窗口最大值 / 最小覆盖子串 / 轮转数组 / 缺失的第一个正数 [打印本页]
作者: 铁佛    时间: 2025-4-29 02:04
标题: 【LeetCode 热题 100】滑动窗口最大值 / 最小覆盖子串 / 轮转数组 / 缺失的第一个正数
    ⭐️个人主页：@小羊     ⭐️所属专栏：LeetCode 热题 100     很荣幸您能阅读我的文章，诚请批评指点，接待接待 ~   


  
子串

和为 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的用户



欢迎光临 qidao123.com技术社区-IT企服评测·应用市场 (https://dis.qidao123.com/) Powered by Discuz! X3.4