力扣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;}};