使用C++编写代码，找到具有相同最小值和最大值的子数组的数量
在程序设计中，常常需要对数组进行各种各样的操作。其中一种常见的操作是寻找具有相同最小值和最大值的子数组数量。这个问题有很多种解法，本文将介绍一种基于哈希表的解法，该解法时间复杂度为O(n)。
哈希表
哈希表是一种常见的数据结构，用于实现快速的查找、插入和删除操作。它通常由一个固定大小的数组和一个哈希函数组成。哈希函数将每个元素的关键字映射到数组中的一个位置，这里也称为哈希桶。如果哈希桶中已经存在其他元素，则会发生哈希冲突。通常有两种解决哈希冲突的方法：
链表法：在哈希桶中维护一个链表，将所有哈希冲突的元素都加入到链表中。在查找元素时，首先根据哈希函数找到对应的哈希桶，然后遍历链表找到对应元素。
开放寻址法：在哈希桶中依次探查位置，找到第一个空位置插入元素。在查找元素时，根据哈希函数找到对应的哈希桶，若该位置为空，则该元素不存在；否则，继续依次探查位置，找到对应元素。
算法步骤
具有相同最小值和最大值的子数组有以下两个特点：
区间最小值等于区间最大值；
区间长度大于等于2。
因此，我们可以先求出以每个元素为结尾的最小值和最大值，然后对于每个最小值和最大值相等的区间，计算其数量即可。
具体实现时，我们可以使用一个哈希表来记录每个最小值和最大值相等的区间数量。遍历数组时，根据当前元素和之前的最小值以及最大值，更新哈希表中对应的值。最后统计哈希表中所有大于等于2的值的和即为答案。
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
const int INF = 0x3f3f3f3f;
int a[N];
int Min[N], Max[N];
int main() {
int n; cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
unordered_map<int,int> mp;
mp[INF] = 1; // 边界条件
int ans = 0;
for (int i = 0; i < n; i++) {
Min[i] = min(a[i], Min[i-1] == INF ? a[i] : Min[i-1]);
Max[i] = max(a[i], Max[i-1] == -INF ? a[i] : Max[i-1]);
if (i > 0 && Min[i] == Max[i]) {
ans += mp[Min[i]];
}
mp[Min[i]]++;
}
cout << ans << endl;
return 0;
}
总结
在本文中，我们介绍了使用哈希表求解具有相同最小值和最大值的子数组数量的算法。该算法基于哈希表，时间复杂度为O(n)。使用哈希表可以快速地统计出具有相同最小值和最大值的区间数量，并且代码也比较简单易懂。
然而，哈希表的空间复杂度很高，需要根据具体问题的需求进行选择。另外，哈希表通常需要解决哈希冲突，这也会带来一定的时间和空间开销。在实际应用中，需要综合考虑各种因素，选择合适的数据结构和算法。