我们先来看个简单的问题。

假如给你20亿个非负数的int型整数，然后再给你一个非负数的int型整数 t ，让你判断t是否存在于这20亿数中，你会怎么做呢？

有人可能会用一个int数组，然后把20亿个数给存进去，然后再循环遍历一下就可以了。

想一下，这样的话，时间复杂度是O(n)，所需要的内存空间

4byte * 20亿，一共需要80亿个字节，

大概需要8GB的内存空间，显然有些计算机的内存一次是加载不了这么这么多的数据的。

初步优化

按照上面的做法，时间复杂度是O(n)，内存是8GB，实际上我们是可以把时间复杂度降低到O(1)的。