Learning to be Giant.

关于Two Sum这道题

|

在Leetcode上面这道题的链接

这道题其实说起来不是一道难题,但是我还是花了一些时间在这个题上面,究其原因是解题的时候一直顺着比较naive的方法在做,而忽视了运用数据结构的重要性,也折射出自己尚不能将算法内化为自己的思维模式的问题。

其实说起来这个题就是用一个hashmap来做两个数字间的映射,但是我刚开始想到的是比较简单的搜索的方法,虽然也考虑了一些优化策略,包括只搜索比target的一半大的数字,使用二分搜索等等,但是毕竟是搜索,所以得到了不少TLE。后来看到discussion里有人讨论hashmap,顿时豁然开朗。

第16行补充判断的原因是避免duplicate,因为重复的项也会被映像到同一个地方,所以需要补充判断。

在这道题之外,还有一个3Sum的问题。由于有了2Sum的经验,我首先考虑使用hashmap。通过hashmap,将这个$O(n^3)$的算法降到$O(n^2)$。

  1. 将元素两两作和,以和的内容作为hashmap的key,两个元素的index作为hashmap的value。注意:由于题目当中要求不允许重复且结果需要升序,这里直接应当避免重复,并预先排序。
  2. 对原数组再次进行一次遍历,将数组元素取相反数在hashmap当中查询。

    这个地方有一个天坑。因为为了避免重复的问题我设置了一个变量叫做prev_i表示之前一次当中i所指向的元素的值。如果当前的元素和prev_i的值相同了,那么应当跳过当前元素,因为题目要求答案中不允许有重复。但是,对于测试用例{-4,-2,-2,-2,0,1,2,2,2,3,3,4,4,6,6},当前两个元素是-4, 2和当前两个元素是-2, 0,对于2(index是6的)这个元素来说,前一种情况按照我的判断条件不会被选中,而后一种情况会被选中,导致这个元素被标记已用过。为了解决这个问题,我们从后向前遍历,由于题目只要求数字不重复,对于具体元素没有要求,我们钻了一个空子。

在discuss当中,我看到了一个两端搜索的方法,感觉非常好,值得学习一下。

与之类似的3Sum Closest,这个题做完之后使用上面提到的这个两端搜索的方法,可以轻松地解决Closest的问题。

总结一下

其实从3Sum的分析,可以知道使用hashmap可以将复杂度减少一个数量级,就算是扩展为4Sum的问题,起码我们可以将其将为$O(n^3)$的问题。利用两端搜索的方法起码也可以降到$O(n^3)$。之余是不是还有更好的方法,还没想到。

Disclaimer: This is a personal weblog. The opinions expressed here represent my own and not those of any entity with which I have been, am now, or will be affiliated.

Comments