2026-03-19：范围与里面和相配的踏实子数组。用go讲话，给定一个整数数组 capacity，请统计其中有几许个邻接区间合乎底下的要求：
• 区间内至少包含 3 个元素；
• 这个区间的第一个数和终末一个数换取；
• 况兼这两个端点的值，恰好等于它们中间系数元素的总和。
换句话说，如若某个子数组的驾驭两头相配，而且这个相配的值刚巧能被中间部分一齐加起来得到，那么这个子数组就看成一个“踏实”子数组。
你的任务是：复返这么的子数组总和。
3
-1000000000
输入： capacity = [9，3，3，3，9]。
输出： 2。
评释：
[9，3，3，3，9] 是踏实数组，因为首尾元素齐是 9，且它们之间元素之和为 3 + 3 + 3 = 9。
[3，3，3] 是踏实数组，因为首尾元素齐是 3，且它们之间元素之和为 3。
题目来独力扣3728。
一、算法举座大体经过（分圭臬详备描写）
圭臬1：界说中枢用具
1. 前缀和数组：prefix[i] 默示数组前i个元素的累加和（快速贪图恣意区间和）；
2. 哈希表（字典）：存储键值对，键是二元组 (现时元素值， 前缀和值)，值是该二元组出现的次数；
作用：快速查找称心条目的左端点L，幸免暴力遍历系数子数组。
圭臬2：开动化变量
1. 开动化谜底计数器：用于统计合乎条目的踏实子数组数目（开动为0）；
2. 开动化前缀和：从数组第一个元素脱手贪图；
3. 开动化哈希表：为空，后续动态存入二元组。
圭臬3：遍历数组（右指针遍历，从第二个元素脱手）
以右指针r代表子数组的右端点，逐一遍历数组元素，中枢逻辑分3步：
1. 查询匹配的左端点
以现时右端点值capacity[r]、现时前缀和为条目，去哈希表中查找：
有莫得左端点L 称心：
• capacity[L] = capacity[r]（首尾相配）；
• prefix[L] + capacity[L] = 前缀和（中间和等于端点值）。
查到的次数，径直累加到谜底计数器中（每一次匹配齐对应一个踏实子数组）。
2. 存入新的二元组到哈希表
将左候选点（现时右指针的前一个元素）的二元组：
(capacity[r-1]， prefix[r-1] + capacity[r-1])
存入哈希表，澳门新浦京计数+1（为后续的右端点提供匹配依据）。
3. 更新前缀和
把现时元素的值加到前缀和中，继续下一轮遍历。
圭臬4：遍历已毕，复返话案
遍历完成后，谜底计数器的值便是系数合乎条目的踏实子数组数目。
二、示例推演（输入 [9，3，3，3，9]）
数组索引：0(9)、1(3)、2(3)、3(3)、4(9)
指标为止：2个踏实子数组 [0，4]、[1，3]
1. 开动：前缀和=9（索引0），哈希表空，OD体育app谜底=0；
2. r=1（元素3）：查询无匹配，存入(9， 9+9=18)，前缀和更新为12；
3. r=2（元素3）：查询无匹配，存入(3， 3+12=15)，前缀和更新为15；
4. r=3（元素3）：查询哈希表，匹配到(3，15)，谜底+1（对应子数组[1，3]），存入(3，3+15=18)，前缀和更新为18；
5. r=4（元素9）：查询哈希表，匹配到(9，18)，谜底+1（对应子数组[0，4]），存入新二元组，前缀和更新为27；
最终谜底=2，与预期一致。
三、时候复杂度 & 独特空间复杂度
1. 时候复杂度
• 算法仅一次遍历数组，遍历次数为数组长度n；
• 哈希表的查询、插入操作齐是平均 O(1) 时候；
• 总时候复杂度：O(n)
• 适配题目要求：数组长度最高10⁵，O(n)算法可高效运行。
2. 独特空间复杂度
• 仅使用了一个哈希表存储二元组；
• 哈希表最多存储n个键值对（遍历中每个元素最多存入一次）；
• 无其他大限制数据结构；
• 总独特空间复杂度：O(n)
回想
1. 算法中枢：前缀和+哈希表，将暴力O(n²)优化为O(n)；
2. 经过：右指针遍历→哈希表查匹配左端点→更新谜底→存入新候选→更新前缀和；
3. 复杂度：时候O(n)，空间O(n)，好意思满适配大数据量的题目要求。
Go完整代码如下：
package main
import (
"fmt"
)
func countStableSubarrays(capacity []int) (ans int64) {
type pair struct{ x， s int }
cnt := map[pair]int{}
sum := capacity[0] // 前缀和
for r := 1; r
ans += int64(cnt[pair{capacity[r]， sum}])
cnt[pair{capacity[r-1]， capacity[r-1] + sum}]++
sum += capacity[r]
}
return
}
func main {
capacity := []int{9， 3， 3， 3， 9}
result := countStableSubarrays(capacity)
fmt.Println(result)
}
Python完整代码如下：
# -*-coding:utf-8-*-
from typing import List
from collections import defaultdict
def count_stable_subarrays(capacity: List[int]) -> int:
"""
贪图踏实子数组的数目
参数:
capacity: 整数列表
复返:
踏实子数组的数目
"""
ans = 0
# 使用字典来存储pair计数，Python中的元组不错径直作为字典键
cnt = defaultdict(int)
# 前缀和
prefix_sum = capacity[0]
# 从索引1脱手遍历
for r in range(1， len(capacity)):
# 查询并累加合乎条目的子数组数目
ans += cnt[(capacity[r]， prefix_sum)]
# 更新计数
cnt[(capacity[r-1]， capacity[r-1] + prefix_sum)] += 1
# 更新前缀和
prefix_sum += capacity[r]
return ans
def main:
# 测试用例
capacity = [9， 3， 3， 3， 9]
result = count_stable_subarrays(capacity)
print(result)
if __name__ == "__main__":
main
C++完整代码如下：
#include
#include
#include
#include
using namespace std;
// 界说pair结构体，用于作为map的键
struct Pair {
int x; // 元素值
int s; // 和/前缀和
// 需要界说相比运算符才智作为map的键
bool operator
if (x != other.x) return x
return s
}
};
long long countStableSubarrays(vector& capacity) {
long long ans = 0;
map
int sum = capacity[0]; // 前缀和
for (int r = 1; r
// 查询并累加合乎条目的子数组数目
ans += cnt[{capacity[r]， sum}];
// 更新计数
cnt[{capacity[r-1]， capacity[r-1] + sum}]++;
// 更新前缀和
sum += capacity[r];
}
return ans;
}
int main {
// 测试用例
vector capacity = {9， 3， 3， 3， 9};
long long result = countStableSubarrays(capacity);
cout
return0;
}
咱们折服东说念主工智能为平庸东说念主提供了一种“增强用具”，并发愤于共享全方针的AI学问。在这里，您不错找到最新的AI科普著述、用具评测、援手成果的诡秘以及行业细察。
迎接心绪“福大大架构师逐日一题”OD体育app官网，发音问可获取口试辛劳，让AI助力您的将来发展。
幸运彩app官方网站下载