一个整数数列，元素取值可能是1~N（N是一个较大的正整数）中的任意一个数，相同数值不会重复出现。设计一个算法，找出数列中符合条件的数对的个数，满足数对中两数的和等于N+1。 复杂度最好是O(n)，如果是O(n2)则不得分。

网上大多数人的做法时间复杂度虽然能达到 O(n), 但是空间复杂度是O(N) ，题目已经指出N是一个较大的整数，所以可能不大好。
想了一下，想了一个空间复杂度是O(m)的算法 ，其中m是输入整数数列的长度。设输入的整数数组是array，符合条件的数对的个数为count，初始化为0
1. 建立hash集合S, 遍历array的前一半元素，对于这一半元素中的任意一个元素e, 在S中插入 N+1 - e
2. 遍历array的后一半元素，对于每一个元素e, 如果e在S中已经存在，则count +1
3. 遍历结束，返回count即可

这个算法只需遍历一遍输入数组，复杂度为O(n) ，只需存储m/2个元素，复杂度为O(m) ,如果m远小于N，这个算法还是有很大改进的。