今日学习记录
1. 3728. 边界与内部和相等的稳定子数组
关键词：前缀和 哈希表
问题分析：
找到满足以下条件的
- 其长度 至少 为 3。
- 首 元素与 尾 元素都等于它们之间所有元素的 和（即
capacity[l] = capacity[r] = capacity[l + 1] + capacity[l + 2] + ... + capacity[r - 1])。
核心思路: 先求出前缀和 pre
式子变形
c[l] = c[r];pre[r]-pre[l] = capacity[l + 1] + capacity[l + 2] + ... + capacity[r - 1]
c[l] = c[r] = pre[r]-pre[l]->pre[r] = pre[l]+c[l]
哈希表
枚举右,维护左,我们要枚举的显然易见是pre[r],要维护的是左pre[l]+c[l],由于pre[i]+c[i]是捆绑的,所以使用 pair<>进行存储,枚举每个右端点pre[r]和c[r] = c[l],再存储到哈希表中数量增加,用答案去累加
tip: 注意pre[l-1]+c[l] = pre[l],可以合并前缀和的代码和哈希表计数
**最终代码：
int n = capacity.size();
map<pair<int,long long>,int> mp;
long long ans = 0;
long long sum = capacity[0];
for(int i = 1;i<n;i++){
ans += mp[{capacity[i],sum}];
mp[{capacity[i-1],capacity[i-1]+sum}]++;
sum += capacity[i];
}
return ans;学到的点：
- 数学推导
- 哈希技巧
思考题
如果把长度至少为 3 改成 4,甚至 k 的情况呢?
思考
原题中的长度至少为3这个信息其实没有用,因为要符合第二个条件,就已经必须要满足长度至少为3了,比如[2,1,2],2 = 2 = 1+1,所以再改为 k 的情况其实才是这个题的完整体,当改为比三更大的长度之后,我们就要手动检查数组下标是否满足条件了,仅此而已
解题思路
我们可以保持之前的所有方法不变,都说了仅此只需要加一个手动检查就行,之前的做法将所有的值累加到 map 中,map 中的都是答案,只是这些答案的下标不知道满不满足r>=l+k,所以可以记录这些下标,然后每次到这个记录下标的数组中找到满足条件的部分,由于下标有单调性,且要找到r>=l+k,所以可以使用二分查找,在进行范围(数组长度减去找到的下标)累加就行了
实现代码
long long countStableSubarrays(vector<int>& capacity) {
int n = capacity.size();
vector<long long> pre(n+1);
for(int i = 1;i<=n;i++){
pre[i] = pre[i-1]+capacity[i-1];
}
map<pair<int,long long>,vector<int>> mp;
for(int i = 0;i<n;i++){
mp[{capacity[i],pre[i]}].push_back(i);
}
long long ans = 0;
for(int l = 0;l<n;l++){
long long t = 2*capacity[l]+pre[l];//pre[r];
auto temp = make_pair(capacity[l],t);
if(mp.count(temp)){
const auto &a = mp[temp];
int pos = ranges::lower_bound(a,l+2)-a.begin();
ans += (a.size()-pos);
}
}
return ans;
}