Skip to content

Latest commit

 

History

History

017. 4Sum

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 
 
 

这道题虽然是一道中等难度的题,但是麻烦程度完全不亚于 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 的使用可能是这个方案里的一个瓶颈,但如果要避免使用它,则需要另一个强大的规律,排除重复序列。

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