题目内容

在一个小镇上，有一个叫做小红的年轻人，他喜欢玩数学游戏和解决难题。

某一天，他拿到了一个整数数组，感到很兴奋，因为他喜欢研究数列和数论。但是，他很快发现这个数组并不像他之前接触过的那些简单的数列。这个数组中的数似乎没有规律可循，让他感到很困惑。

题目思路

1.自然考虑双重循环，复杂度$O(n^2)$不允许。

2.发现一个关键性质:$a_i$的和小于等于$1e5$ , 那么对$a_i$ 去重之后不同数的个数最多为$\sqrt{1e5}$个。 发现这个性质以后，可以直接对去重后的集合双重循环暴力。显然复杂度$O(值域)$ ，可过本题。

代码

Python代码