一. 区间合并、插入、重叠数
二. 区间内满足条件的点对、区间和、偏序关系数（树状数组和前缀和）
三. 排序贪心问题
四 . 统计满足条件的子数组（哈希+前缀和）
1. 统计中位数为k的子数组
2. 连续数组
含有相同数量的0和1的最长连续子数组
class Solution {
public:
int findMaxLength(vector<int>& nums) {
map<int,int> m;
int n = nums.size();
for(int i=0,presum=0;i<n;i++){
presum+=nums[i]==0?-1:1;
m[presum] = i;
}
int maxlen = 0;
for(int i=0,presum=0;i<n;i++){
if(m.count(presum)){
if(m[presum]-i+1>maxlen)
maxlen = m[presum]-i+1;
}
presum+=nums[i]==0?-1:1;
}
return maxlen;
}
};
3. 使数组和能被 P 整除
移除最短子数组（也就是求区间和为sum-p）
class Solution {
public:
int minSubarray(vector<int>& nums, int p) {
int sum = 0;
for (auto num : nums)
sum = (sum + num) % p;
if (sum == 0) return 0;//不用去除任何数
//求区间和等于满足p-sum
map<int, int> m;
int presum = 0, res = nums.size();
for (int i = 0; i < nums.size(); i++) {
m[presum] = i;
presum = (presum + nums[i]) % p;
if (m.count((presum-sum+p) % p))
res = min(res, i - m[(presum - sum + p) % p] + 1);
}
return res == nums.size() ? -1 : res;
}
};
4. 和可被 K 整除的子数组
也就是求和为k/-k/0的子数组（预处理）
class Solution {
public:
int subarraysDivByK(vector<int>& nums, int k) {
map<int,int> m;
int presum = 0;
int cnt = 0;
m[0] = 1;
for(int &num:nums){
presum+=num;
presum%=k;
if(m.count(presum)) cnt = cnt + m[presum];
if(m.count(presum+k)) cnt = cnt + m[presum+k];
if(m.count(presum-k)) cnt = cnt + m[presum-k];
m[presum]++;
}
return cnt;
}
};
5. 表现良好的最长时间段
等价于求1数目大于0数目的最长子区间
class Solution {
public:
int longestWPI(vector<int>& hours) {
int n = hours.size();
unordered_map<int, int> m;
int presum = 0, res = 0;
for (int i = 0; i < n; i++) {
presum += hours[i] > 8 ? 1 : -1;
if (presum > 0)
res = max(res, i + 1);//最长长度
else {
if (m.count(presum - 1))
res = max(res, i - m[presum - 1]);
}
if (!m.count(presum)) m[presum] = i;//记录最左端值
}
return res;
}
};