由 數正方形 到 Map, Hash, Set

事源是發生在 pku 2002 Squares，和 gguy 剛做了的 pku 3432 Count Squares

題目大意是有 N 點，問 N 點中有多少個正方形 ?

對於已知的兩點，可能組成的正方形只有兩個，

我的方法是兩個 for loops，然後看看這兩點對應可能組成的正方形的另外兩點是否存在。

所以 time complexity 是 O(n*n*?)。 ? depend on the method you implemented.

我試了三種方法，

1) Map，把 point map 去 bool，試時看看 map 完後是否 return true ;

2) Hash，把 point 用 hash 放入 array 中，試時看看找不找到該 point ;

3) Set，把 point 放入 set，試時看看該 point 是否在 set 之中;

結果

1) Map => TLE ，不知 time complexity

2) Hash => Accept , 超快 ，O(1)

3) Set => Accept , 中速， O(logN)

數據如下 :

===================================

Result Memory Time Code Length
Set AC 476K 3000MS 517B
Hash AC 1388K 641MS 1081B
Map TLE 684B

===================================

Map 不是不好，只是在這情況下這樣用 Map 不好，
當 array 可能要開到 a[1000000000]時，但又不是每個元素都用得著，
這時用 Map 模仿 array ，可以省下很多 Memory。

另外，也難保有第二種方法用 Map 可以在這題表現得比 Set 好。

===================================

Map 基本用法 :
1) include map