返回信息流给定一个数组，如何快速判断数组中的两个数的和也在数组中。
比如，1，2，3；1在数组中，2在数组中，他们的和3也在数组中。
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #95126同步于 2018/3/19
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
阿里面试算法题求指导，数组题
Samuelyo
2018/3/19镜像同步29 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
您好，能不能麻烦您说的详细一点呢？我回答的时间复杂度是n2，让我再优化就没有想出更好的了，谢谢您
【 在 lucashood 的大作中提到: 】
: 这个跟two sum一个思路啊
:
: 把数组里的元素放大一个dict里，然后每次求完和去dict里查找
我用Python简单写了个算法，你看下，那个x和y就是你从数组里取的值，d是一个字典，遍历一遍数组，将元素i当成字典的key，字典的value的话随意，反正也不用它，之后求和得到z，然后去字典中查找z，如果查到，返回true，否则返回false
【 在 Samuelyo (Samuelyo) 的大作中提到: 】
: 您好，能不能麻烦您说的详细一点呢？我回答的时间复杂度是n2，让我再优化就没有想出更好的了，谢谢您
我能想到的
1、枚举可能出现的和，组成新数组，取交集，时间n^2，空间n^2
2、时间换一下空间，不组成新数组，每次暴力从头找到尾，时间n^3，空间1
3、空间换一下时间，用multimap，来一个就对容器里已有的遍历一遍并依次求和，对结果判断是否在容器内，时间n^2*logn，空间n
4、优化一下2，先排序，然后用三指针思路，左边指针外循环，中右指针内循环，和比右指针小时中指针++，大时右指针—，时间n^2，空间1
有错误请指正，求轻喷