小强有一个长度为的数组和正整数.
他想请你帮他计算数组中有多少个连续子区间[l,r],其区间内存在某个元素出现的次数不小于次?
例如数组且,那么区间[1,3],[1,4],[1,5],[2,4],[2,5]都是满足条件的区间,但区间[3,4]等都是不满足条件的.
第一行输入两个正整数和.
第二行输入n个正整数.
输出一个整数表示答案.
5 2 1 2 1 2 3
5
满足条件的区间为[1,3],[1,4],[1,5],[2,4],[2,5].
#include <bits/stdc++.h> typedef long long ll; using namespace std; int n,m,a; ll ans=0; vector<int>v[400005]; int main() { ios::sync_with_stdio(0),cin.tie(0); int i,j=1,best=0; cin>>n>>m; for(i=1;i<=n;i++) { cin>>a;/**< a值下标存储在v[a]中 */ v[a].push_back(i); /**< 第i个位置时a的数量达到了m,将i作为右端点此时a的第一个位置及其之前的位置都满足条件 */ if(v[a].size()==m) { /**< 我们取满足条件的数字中下标最靠右的 */ best=max(best,v[a][0]); v[a].erase(v[a].begin()); } ans+=best; } cout<<ans; return 0; }
def judge(aa, m): list1 = [] for i in range(len(aa)): cnt1 = 0 for j in range(len(aa)): if aa[i] == aa[j]: cnt1 += 1 list1.append(cnt1) if max(list1) >= m: return True else: return False inp = input().split() n = int(inp[0]) m = int(inp[1]) a = input().split() cnt = 0 for i in range(n-1): for j in range(i+1, n): if judge(a[i: j+1], m) == True: cnt += 1 print(cnt)
n, m = map(int, input().split()) arr = list(map(int, input().split())) cnt = [0] * (n + 5) cnt[arr[0]] = 1 r, ans = 1, 0 for l in range(1, n + 1): if r <= n and cnt[arr[r - 1]] < m: r += 1 while r <= n: cnt[arr[r - 1]] += 1 if cnt[arr[r - 1]] >= m: break r += 1 ans += (n - r + 1) cnt[arr[l - 1]] -= 1 print(ans)
滑动窗口去处理,但是要注意一个子区间满足时,要不断移动左边界,计算符合要求的全部区间。例如m = 2,nums = [1,2,1,3,4]时,滑动窗口刚刚覆盖[1,2,1]时满足要求,但是[1,2,1,3],[1,2,1,3,4]同时也满足要求。
import java.util.*; public class Main { public static void main(String[] args) { Scanner s = new Scanner(System.in); int len = s.nextInt(), m = s.nextInt(); int[] nums = new int[len]; for (int i = 0; i < len; i++) { nums[i] = s.nextInt(); } int left = 0; long ans = 0; Map<Integer, Integer> map = new HashMap<>(); boolean find = false; for (int right = 0; right < len; right++) { int times = map.getOrDefault(nums[right], 0); times++; map.put(nums[right], times); if (times == m) { find = true; } while (find) { ans += len - right; int leftTimes = map.get(nums[left]); leftTimes--; map.put(nums[left], leftTimes); if (nums[left] == nums[right] && leftTimes < m) { find = false; } left++; } } System.out.println(ans); } }
#include<iostream> #include<algorithm> #include<vector> #include<unordered_map> using namespace std; int main(){ int n = 0, m=0; cin>>n>>m; vector<int> nums(n); for(int i =0;i<n;i++){ cin>>nums[i]; } long long left = 0, right = 0, res = 0; unordered_map<int, int> mymap; mymap[nums[right]]++; while(left<n){ while(mymap[nums[right]]<m){ right ++; if(right == n) break; mymap[nums[right]] ++; } if(right == n){ break; } res += (n - right); mymap[nums[left]]--; left++; } cout<<res<<endl; return 0; }
#include <bits/stdc++.h> using namespace std; using ll = long long; int n,m; int main(){ ios::sync_with_stdio(false); cin.tie(0); while(cin >> n >> m){ vector<int> a(n); for(int i = 0;i < n;i++){ cin >> a[i]; } //先找到刚好只有一个最大重复为m的所有区间。每个区间求向后的区间数 unordered_map<int,int> cnt; ll res = 0; int l = 0, r = 0; while(r < n){ cnt[a[r]]++; while(l<=r && cnt[a[r]] >= m){ res += (n-r); cnt[a[l]]--; l++; } r++; } printf("%ld\n", res); } }经典滑动窗口。但是我被这题创死了。原因是,结果是长整型,一般的题目不应该提示取模吗?可见出题者不讲武德。然后边界条件l<=r错了。
import sys import math a = input().split() n = int(a[0]) m = int(a[1]) a = list(int(i) for i in input().split()) res = 0 i = 0 dic = dict() j = 0 while j < n: try: dic[a[j]] += 1 except: dic[a[j]] = 1 while dic[a[j]] == m: res += n-j dic[a[i]] -= 1 i += 1 j += 1 print(res)
import java.util.HashMap; import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int m = in.nextInt(); int[] list = new int[n]; for(int i=0;i<n;++i){ list[i]=in.nextInt(); } long ans=0; int i=0,j=0; HashMap<Integer, Integer> hashMap=new HashMap<>(); while(j<n){ if(!hashMap.containsKey(list[j])){ hashMap.put(list[j],1); } else { hashMap.put(list[j], hashMap.get(list[j]) + 1); } while (hashMap.get(list[j]) >= m) { ans += (long)(n - j); hashMap.put(list[i], hashMap.get(list[i]) - 1); i++; } j++; } System.out.println(ans); in.close(); } }
n, m = map(int, input().split()) nums = list(map(int, input().split())) from collections import defaultdict counter = defaultdict(int) res = 0 j = 0 for i in range(n): counter[nums[i]] += 1 while counter[nums[i]] == m: counter[nums[j]] -= 1 j += 1 res += j print(res)
#include <iostream> #include <unordered_map> #include <deque> using namespace std; unordered_map<int, deque<int>> f; long long ans = 0; int n, m; int main() { ios::sync_with_stdio(0), cin.tie(0); cin >> n >> m; int satisfy = 0; for(int i = 1; i <= n; i ++ ) { int x; cin >> x; f[x].push_back(i); if(f[x].size() == m) { satisfy = max(satisfy, f[x][0]); f[x].pop_front(); } ans += satisfy; } cout << ans; return 0; }
#include<bits/stdc++.h> using namespace std; int main(){ uint64_t res = 0; int n, m; cin >> n >> m; int nums[n]; for(int i = 0;i < n; i++) { cin >> nums[i]; } unordered_map<int, int> cnt; for(int right = 0, left = 0; right < n; right++) { if(++cnt[nums[right]] == m) { res += (n-right); //当左窗口右缩的时候不用担心 m = 2 [4 3 1 2 1 2 3 7] //像 3 3会被漏算的情况 会被算进去的 //小于等于是因为 m = 1 的样例 while(left <= right && cnt[nums[right]] >= m) { cnt[nums[left]]--; left++; if(cnt[nums[right]] == m) { res += (n-right); } } } } cout << res; return 0; }
from collections import defaultdict n, m = list(map(int, input().split())) arr = list(map(int, input().split())) mem = defaultdict(int) ans = 0 i,j = 0,0 max_num = 0 while j < n: mem[arr[j]] += 1 max_num = max(max_num, mem[arr[j]]) if max_num == m: while max_num == m: ans += n-j if mem[arr[i]] == max_num: max_num -= 1 mem[arr[i]] -= 1 i += 1 j+=1 print(ans)
public static void main(String[] args) { //输入 Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int[] a = new int[n]; for(int i = 0; i < n; i++){ a[i] = sc.nextInt(); } //处理 Map<Integer,Integer> map = new HashMap<>(); int res = 0; int l = 0, r = 0; while (r < n){ map.put(a[r], map.getOrDefault(a[r], 0)+1); while(l <= r && map.get(a[r]) >= m){//满足要求的区间 res += n - r; map.put(a[l],map.get(a[l])-1); l--; } r++; } //输出 System.out.println(res); }
#include<bits/stdc++.h> #define int long long using namespace std; int a[600000]; int cnt[600000]; signed main() { int n, m; cin >> n >> m; for (int i = 1; i <= n; ++i) { cin >> a[i]; } int ans = 0; int pre = 1; for (int i = 1, j = 0;;) { do { if (j >= n) break; cnt[a[++j]]++; }while (cnt[a[j]] < m); while (cnt[a[j]] >= m) { if (a[i] != a[j]) { cnt[a[i]]--; i++; } else break; } if (cnt[a[j]] >= m) ans += (i-pre+1) * (n - j + 1); // cout << i << ' ' << j << endl; if (j >= n) break; cnt[a[i]]--;i++; pre = i; } cout << ans << endl; }
import java.util.ArrayList; import java.util.HashMap; import java.util.HashSet; import java.util.Scanner; /** * @auther slience */ public class Main { public static long solve(int[] arr,int m){ long res = 0; // 存放每个数出现的次数 HashMap<Integer,Integer> map1 = new HashMap<>(); HashSet<Integer> set = new HashSet<>(); int L=0; int R=L; while (L<arr.length){ while(R<arr.length&&(set.size()==0)) { if (map1.containsKey(arr[R])) { map1.put(arr[R], map1.get(arr[R]) + 1); } else { map1.put(arr[R], 1); } if (map1.get(arr[R]) >= m) { set.add(arr[R]); } R++; } if(set.size()!=0){ res+=arr.length-R+1; } map1.put(arr[L],map1.get(arr[L])-1); Integer number = map1.get(arr[L]); if(number<m){ set.remove(arr[L]); } L++; } return res; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int m = scanner.nextInt(); int[] arr =new int[n]; for(int i=0;i<arr.length;i++){ arr[i]=scanner.nextInt(); } System.out.println(solve(arr, m)); } }大致思路:双指针模拟过程 解题 常坑人点用long接住