子數(shù)組：指在一個數(shù)組中，選擇一些連續(xù)的元素組成的新數(shù)組。

例題一：6900. 統(tǒng)計完全子數(shù)組的數(shù)目

給你一個由?正?整數(shù)組成的數(shù)組?nums?。

如果數(shù)組中的某個子數(shù)組滿足下述條件，則稱之為?完全子數(shù)組?：

• 子數(shù)組中?不同?元素的數(shù)目等于整個數(shù)組不同元素的數(shù)目。

返回數(shù)組中?完全子數(shù)組?的數(shù)目。

子數(shù)組?是數(shù)組中的一個連續(xù)非空序列。

示例 1：

輸入：nums = [1,3,1,2,2]
輸出：4
解釋：完全子數(shù)組有：[1,3,1,2]、[1,3,1,2,2]、[3,1,2] 和 [3,1,2,2] 。

示例 2：

輸入：nums = [5,5,5,5]
輸出：10
解釋：數(shù)組僅由整數(shù) 5 組成，所以任意子數(shù)組都滿足完全子數(shù)組的條件。子數(shù)組的總數(shù)為 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) { // 枚舉子數(shù)組右端點 v=nums[i]cnt[v]++;while (cnt.size() == m) {int x = nums[left++];if (--cnt[x] == 0)cnt.erase(x);}ans += left; // 子數(shù)組左端點 < left 的都是合法的}return ans;}
};

例題二：5057. 截斷數(shù)組

給定一個長度為?n?的正整數(shù)數(shù)組a1,a2,…,an?和一個正整數(shù)?p。

現(xiàn)在，要將該數(shù)組從中間截斷，得到兩個非空子數(shù)組。

我們規(guī)定，一個數(shù)組的價值等于數(shù)組內所有元素之和模?p?的結果。

我們希望，將給定數(shù)組截斷后，得到的兩個非空子數(shù)組的價值之和盡可能大。

請你輸出這兩個非空子數(shù)組的價值之和的最大可能值。

輸入格式

第一行包含兩個整數(shù)?n?和?p。

第二行包含?n個整數(shù)?a1,a2,…,an。

輸出格式

一個整數(shù)，表示價值之和的最大可能值。

數(shù)據范圍

前?33?個測試點滿足?2≤n≤10。
所有測試點滿足?2≤n≤1e5，2≤p≤10000，1≤ai≤1e6。

輸入樣例1：

4 10
3 4 7 2

輸出樣例1：

16

輸入樣例2：

10 12
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;
}

今日推薦音樂：落單戀人

下一篇：Codeforces Round 889 (Div. 2)