美团笔试
美团笔试第四题
自认为写了个 O(n2)的解法，但是还是 过不去所有，超时
是因为dict的复杂度问题吗
import sys
n = sys.stdin.readline().strip()
n = int(n)
nums = list(map(int,sys.stdin.readline().strip().split()))
cnt = 0
dic = {}
a = set(nums)
# for i in range(len(nums)):
for num in a:
if num not in dic:
tmp = [0]*len(nums)
# if nums[0]==nums[i]:
# dic[nums[i]][0]=1
for j in range(len(nums)):
if nums[j] == num:
tmp[j] = tmp[j-1]+1
else:
tmp[j] = tmp[j-1]
dic[num] = tmp
# print(dic)
for i in range(len(nums)-2):
for j in range(i+1,len(nums)-1):
if 3*nums[j]-nums[i] in dic:
tmp = dic[3*nums[j]-nums[i]]
cnt+=tmp[-1]-tmp[j]
# for k in range(j+1,len(nums)):
# if nums[i]+nums[k]==3*nums[j]:
# cnt+=1
print(cnt) 
