leetcode sum问题

注意: 二元组的结果不会重复

方法:

a)暴力求解:时间复杂度O(n*n)

b)使用unordered_map来进行求解 时间复杂度O(n)

要点:

这里使用unordered_map和map都可以

考虑思路使用unordered_set, 由于类对象不能直接被hash?  放弃

hashmap是平均O(1),map是平均O(lnN)的,实践上并不总是如此,有一下几点需要考虑:

hashmap的hash算法是不是需要经过复杂的计算。

一般在数据量小的情况下,unordered_map的性能不如map的


变种问题:


时间复杂度O(n)

数组已经被排序,此时使用之前的方法依然奏效

思路:

a) 考虑左右哨兵,移动哨兵

b)考虑依旧使用unordered_map之类的stl来进行



3.

只有需要得到unique组合的需要考虑到跳过重复元素

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容