这道题虽然是一道中等难度的题,但是麻烦程度完全不亚于 Hard 难度的。
这道题我拖延了三天,总共提交了有近 20 次,从最笨的方法开始尝试,直到现在这个方案。
这个方案,是我得出,最简单,最直观,效率最高的方案。(注意,我说的效率最高是我自己的20次提交中,效率排名是很靠后的)
说到这里,我很好奇那些 100 ms 以内的方案是怎样的,如果有谁知道,希望发 issue 告知~
说说我的心路历程:
首先,是选择数据结构,在这个阶段,我彻底知道了以下几个标准库中的数据结构有多么的废:
unordered_multimap
, 坑在于:你甚至无法按照 key 去迭代!!! 想取出同一个 key 下的 value,甚至需要bucket_count
.unordered_set
, 坑在于:除了 POD 类型,其他类型的 key 你需要自己设计 hash 因子。unordered_multiset
, 总和上述两大坑,这个可以不用试了。
有人说,1 用的难受还可以理解,2 的话,自己设计个 hash 函数有啥难的。并不难,但就是啰嗦加麻烦。 尤其是针对 LeetCode,你会在面试的时候,轻易提出自己来设计个 hash 函数来解决吗?这不是自己挖坑往里面跳吗。
所以我宁愿选择 unordered_map<int, vector<pair<int, int>>>
这个数据结构来作为缓存。
(可以试试为 vector<pair<int, int>> 设计一个 hash 函数。)
选定这个,我开始下面的尝试:
- hash 表里直接存值。
- 不对 num 排序,一排序就至少是 O(n) 没了。但不排序,意味着:
- 插入 vector 前要处理 pair 顺序
- 迭代缓存时,对于去重手足无措
- 迭代缓存时,甚至会出现错误数据,完全无法甄别
- 排序 num,解决了 pair 排序的烦恼,但迭代缓存,依旧很麻烦,容易出现错误数据。
- 不对 num 排序,一排序就至少是 O(n) 没了。但不排序,意味着:
- hash 表里存的是 index,并对 num 排序。(因为如果不排序,index 毫无意义)
为什么要存 index, 举例:
-2 -1 0 0 1 2
-------------
0 1 2 3 4 5
^ ^
- index[1,3,2,4] --> [-1 0 0 1]
- index[1,2,3,4] --> [-1 0 0 1]
如果存值,我们无法区分上述两个子序列,去重将会非常麻烦。更麻烦的是,对于 pari(-1, 0)
与 pair(0, 1)
来说,
是否认为它俩可以合并为一个结果?如果认为不可以,将失去 [-1,0,0,1] 这个序列;如果认为可以,那么就可能会出现 [-2,-1,-1,0] 这样明显非法的序列。
而 index,前后非常清楚,可以找到一个定律:
low.second < high.first --> {low.first, low.second, high.first, high.second} 为要求的序列。
根据以上各种挫折,我发现,先应将所有 pair 存入缓存中。(无脑存即可,存时去重,得不偿失)
取的时候,迭代 key, 将当前 key 作为 low 的 pair, 将 find(target - key) 作为 high 的 pair,然后根据上述定律来甄别结果。
这样做的确清晰简单,而且无比正确。但问题在于无法去重。
这个问题我只好选择使用 set
这个性价比超高的容器,于是得到了现在这个解决方案。
当然我也知道,set
的使用可能是这个方案里的一个瓶颈,但如果要避免使用它,则需要另一个强大的规律,排除重复序列。
各位路过的大侠,有知道的,良心好的,提点提点我吧。