C++ 解法, 执行用时: 137ms, 内存消耗: 9640K, 提交时间: 2023-08-12 10:25:33

#include<bits/stdc++.h>
using namespace std;
string a[100005];
int main(){
	int n,k,i;
	long long sun=0;
	cin>>n>>k;
	map<string,int>m;
	for(i=1;i<=n;i++)
	{
		cin>>a[i];
		sun=sun+m[a[i]];
		m[a[i]]++;
		if(i>k+1)
		m[a[i-k-1]]--;
	}
	cout<<sun<<endl;
}

Python3 解法, 执行用时: 210ms, 内存消耗: 15388K, 提交时间: 2023-08-12 10:25:12

n,k=list(map(int,input().split()))
a=input().split()
d={}
ans=0
for i in range(n):
    if a[i] in d:
        ans+=d.get(a[i])
        d[a[i]]+=1
    else:
        d[a[i]]=1
    if i-k-1>=0:
        d[a[i-k-1]]-=1
print(ans)