子数组：指在一个数组中，选择一些连续的元素组成的新数组。
例题一：6900. 统计完全子数组的数目
给你一个由 正 整数组成的数组 nums 。
如果数组中的某个子数组满足下述条件，则称之为 完全子数组 ：
子数组中 不同 元素的数目等于整个数组不同元素的数目。
返回数组中 完全子数组 的数目。
子数组 是数组中的一个连续非空序列。
示例 1：
输入：nums = [1,3,1,2,2]
输出：4
解释：完全子数组有：[1,3,1,2]、[1,3,1,2,2]、[3,1,2] 和 [3,1,2,2] 。
示例 2：
输入：nums = [5,5,5,5]
输出：10
解释：数组仅由整数 5 组成，所以任意子数组都满足完全子数组的条件。子数组的总数为 10 。
提示：
1 <= nums.length <= 1000
1 <= nums[i] <= 2000
思路：1.用set以及unerdered_set容器暴力枚举
2.滑动窗口
AC代码：
//暴力 class Solution { public: int countCompleteSubarrays(vector<int>& nums) { int sum=0; set<int> s; for(auto& x:nums) s.insert(x); int l=nums.size(); for(int i=0;i<l;i++) { unordered_set<int> ss; for(int j=i;j<l;j++) { ss.insert(nums[j]); if(s.size()==ss.size()) sum++; } } return sum; } };
//滑动窗口 class Solution { public: int countCompleteSubarrays(vector<int> &nums) { int m = unordered_set<int>(nums.begin(), nums.end()).size(); unordered_map<int, int> cnt; int ans = 0, left = 0; for (int v: nums) { // 枚举子数组右端点 v=nums[i] cnt[v]++; while (cnt.size() == m) { int x = nums[left++]; if (--cnt[x] == 0) cnt.erase(x); } ans += left; // 子数组左端点 < left 的都是合法的 } return ans; } };
例题二：5057. 截断数组
给定一个长度为 n 的正整数数组a1,a2,…,an 和一个正整数 p。
现在，要将该数组从中间截断，得到两个非空子数组。
我们规定，一个数组的价值等于数组内所有元素之和模 p 的结果。
我们希望，将给定数组截断后，得到的两个非空子数组的价值之和尽可能大。
请你输出这两个非空子数组的价值之和的最大可能值。
输入格式
第一行包含两个整数 n 和 p。
第二行包含 n个整数 a1,a2,…,an。
输出格式
一个整数，表示价值之和的最大可能值。
数据范围
前 33 个测试点满足 2≤n≤10。
所有测试点满足 2≤n≤1e5，2≤p≤10000，1≤ai≤1e6。
输入样例1：
1. 4 10 2. 3 4 7 2
输出样例1：
16
输入样例2：
1. 10 12 2. 16 3 24 13 9 8 7 5 12 12
输出样例2：
13
思路：前缀和+枚举
AC代码：
#include<bits/stdc++.h> using namespace std; #define int long long const int N = 1e5+10; int a[N],n,p,sum[N],ans; int sumn; void solve() { cin>>n>>p; for(int i=0;i<n;i++){ cin>>a[i]; sumn += a[i]; } sum[0] = a[0]; for(int i=1;i<n;i++){ sum[i] = sum[i-1]+a[i]; } if(n == 2){ int cnt = a[0] % p + a[1] % p; cout<<cnt<<endl; return ; } for(int i=1;i<n-1;i++){ int tmp = sum[i-1]%p+(sumn-sum[i-1])%p; ans = max(ans,tmp); } cout<<ans<<endl; return ; } signed main() { int t=1; while(t--) solve(); return 0; }
