017. 4Sum

这道题虽然是一道中等难度的题，但是麻烦程度完全不亚于 Hard 难度的。

这道题我拖延了三天，总共提交了有近 20 次，从最笨的方法开始尝试，直到现在这个方案。

这个方案，是我得出，最简单，最直观，效率最高的方案。（注意，我说的效率最高是我自己的20次提交中，效率排名是很靠后的）

说到这里，我很好奇那些 100 ms 以内的方案是怎样的，如果有谁知道，希望发 issue 告知～

---

说说我的心路历程：

首先，是选择数据结构，在这个阶段，我彻底知道了以下几个标准库中的数据结构有多么的废：

1. unordered_multimap, 坑在于：你甚至无法按照 key 去迭代!!! 想取出同一个 key 下的 value，甚至需要 bucket_count.
2. unordered_set, 坑在于：除了 POD 类型，其他类型的 key 你需要自己设计 hash 因子。
3. unordered_multiset, 总和上述两大坑，这个可以不用试了。

有人说，1 用的难受还可以理解，2 的话，自己设计个 hash 函数有啥难的。并不难，但就是啰嗦加麻烦。 尤其是针对 LeetCode，你会在面试的时候，轻易提出自己来设计个 hash 函数来解决吗？这不是自己挖坑往里面跳吗。

所以我宁愿选择 unordered_map<int, vector<pair<int, int>>> 这个数据结构来作为缓存。

（可以试试为 vector<pair<int, int>> 设计一个 hash 函数。）

选定这个，我开始下面的尝试：

1. hash 表里直接存值。
   1. 不对 num 排序，一排序就至少是 O(n) 没了。但不排序，意味着：
      1. 插入 vector 前要处理 pair 顺序
      2. 迭代缓存时，对于去重手足无措
      3. 迭代缓存时，甚至会出现错误数据，完全无法甄别
   2. 排序 num，解决了 pair 排序的烦恼，但迭代缓存，依旧很麻烦，容易出现错误数据。
2. 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 的使用可能是这个方案里的一个瓶颈，但如果要避免使用它，则需要另一个强大的规律，排除重复序列。

各位路过的大侠，有知道的，良心好的，提点提点我吧。