注意: 二元組的結(jié)果不會(huì)重復(fù)
方法:
a)暴力求解:時(shí)間復(fù)雜度O(n*n)
b)使用unordered_map來(lái)進(jìn)行求解 時(shí)間復(fù)雜度O(n)
要點(diǎn):
這里使用unordered_map和map都可以
考慮思路使用unordered_set, 由于類對(duì)象不能直接被hash? ?放棄
hashmap是平均O(1),map是平均O(lnN)的,實(shí)踐上并不總是如此吝镣,有一下幾點(diǎn)需要考慮:
hashmap的hash算法是不是需要經(jīng)過(guò)復(fù)雜的計(jì)算堤器。
一般在數(shù)據(jù)量小的情況下,unordered_map的性能不如map的
變種問(wèn)題:
時(shí)間復(fù)雜度O(n)
數(shù)組已經(jīng)被排序末贾,此時(shí)使用之前的方法依然奏效
思路:
a) 考慮左右哨兵闸溃,移動(dòng)哨兵
b)考慮依舊使用unordered_map之類的stl來(lái)進(jìn)行
3.
只有需要得到unique組合的需要考慮到跳過(guò)重復(fù)元素