内存限制 1 GB，如何快速判断一个数是否存在于 40 亿整数中？

这不简单吗？

直接把40亿个整数加载到内存中，然后判断遍历整个列表，看是否存在该整数

此种方式需要占用的内存空间：40 * 100000000 * 4 / 1024 / 1024 / 1024 约等于 15GB，远大于内存限制，并且查询的时间复杂度是O(N)

那么再想想有没有其他办法呢？

再次理解题目，题目要求的是判断一个整数是否存在，而不是求一个整数出现了几次的问题，所以我们根本不用关心这个整数是啥，只用判断是否存在即可

一个整数存不存在完全可以用一个二进制位来表示，比如1代表存在，0代表不存在（BitMap）

那么我们如何在内存中维护整数和二进制位之间的关系呢？

可以用数组来存储，数组的索引表示整数，数组存放的值表示是否存在，如下图所示

此时需要占用的内存空间：2^32 / 8 / 1024 / 1024 / 1024 约等于 512MB，符合内存限制的要求，并且查询的时间复杂度为O(1)