力扣2762. 不间断子数组

力扣2762. 不间断子数组

multiset法

• multiset：元素从小到大排序

  • begin()返回头指针 (最小)
  • rbegin()返回尾指针 (最大)

•   class Solution {public:long long continuousSubarrays(vector<int>& nums) {int n = nums.size();long long res = 0;multiset<int> s;for(int i=0,j=0;i<n;i++){   s.insert(nums[i]);while(*s.rbegin() - *s.begin() > 2){s.erase(s.find(nums[j++]));}res += i-j+1;}return res;}};
  

哈希表法

• map：记录出现次数

  • 同样的rbegin和begin

•   class Solution {public:long long continuousSubarrays(vector<int>& nums) {int n = nums.size();long long res = 0;map<int,int> cnt;for(int i=0,j=0;i<n;i++){   cnt[nums[i]] ++;while(cnt.rbegin()->first - cnt.begin()->first > 2){if(-- cnt[nums[j]] == 0) cnt.erase(nums[j++]);}res += i-j+1;}return res;}};