一個(gè)整數(shù)數(shù)列，元素取值可能是1~N（N是一個(gè)較大的正整數(shù)）中的任意一個(gè)數(shù)，相同數(shù)值不會(huì)重復(fù)出現(xiàn)。設(shè)計(jì)一個(gè)算法，找出數(shù)列中符合條件的數(shù)對(duì)的個(gè)數(shù)，滿足數(shù)對(duì)中兩數(shù)的和等于N+1。 復(fù)雜度最好是O(n)，如果是O(n2)則不得分。

網(wǎng)上大多數(shù)人的做法時(shí)間復(fù)雜度雖然能達(dá)到 O(n), 但是空間復(fù)雜度是O(N) ，題目已經(jīng)指出N是一個(gè)較大的整數(shù)，所以可能不大好。
想了一下，想了一個(gè)空間復(fù)雜度是O(m)的算法 ，其中m是輸入整數(shù)數(shù)列的長度。設(shè)輸入的整數(shù)數(shù)組是array，符合條件的數(shù)對(duì)的個(gè)數(shù)為count，初始化為0
1. 建立hash集合S, 遍歷array的前一半元素，對(duì)于這一半元素中的任意一個(gè)元素e, 在S中插入 N+1 - e
2. 遍歷array的后一半元素，對(duì)于每一個(gè)元素e, 如果e在S中已經(jīng)存在，則count +1
3. 遍歷結(jié)束，返回count即可

這個(gè)算法只需遍歷一遍輸入數(shù)組，復(fù)雜度為O(n) ，只需存儲(chǔ)m/2個(gè)元素，復(fù)雜度為O(m) ,如果m遠(yuǎn)小于N，這個(gè)算法還是有很大改進(jìn)的。