拼多多暑期实习笔试题（4.10），AC3题

n=int(input())
nums=list(map(int,input().strip().split()))
def solution(nums):
    nums=sorted(nums)[::-1]
    n=len(nums)//3
    res=0
    for i in range(len(nums)):
        if (i+1)%3!=0:
            res+=nums[i]
    return res
print(solution(nums))

def solution(nums,M):
    record={0:1}#表示前缀合除以M后的余数为0的有1个
    res=0
    presum=0
    for i in range(len(nums)):
        presum+=nums[i]   #presum 表示i项和，presum减去之前的presum可得某一个连续子数组和
        residual=presum%M
        res+=record.get(residual,0)
        if record.get(residual,0)==0:
            record[residual]=1
        else:
            record[residual]+=1
    return res
N,M=list(map(int,input().strip().split()))
nums=list(map(int,input().strip().split()))
print(solution(nums,M))

from collections import defaultdict
def solution(nums,k):
    res=0
    visited=defaultdict(list)
    for i in range(len(nums)):
        visited[nums[i]].append(i) #用字典记录每个字符出现在哪些索引
    for  value in visited.values():
        distance=[value[i]-value[i-1]-1 for i in range(1,len(value))] #计算将索引i和索引j连在一起需要移除的字符数
        tmp=helper(distance,k)+1  
        res=max(res,tmp)
    return res
def helper(distance,k):  #通过滑动窗口法计算最多移除k个的情况下可以连在一起的长度
    res=0
    l=0
    total=0
    for i in range(len(distance)):
        total+=distance[i]
        while total>k:
            total-=distance[l]
            l+=1
        res=max(res,i-l+1)
    return res

n,k=list(map(int,input().strip().split()))
nums=list(map(int,input().strip().split()))
print(solution(nums,k))