一個整數數列，元素取值可能是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，這個算法還是有很大改進的。