Tuesday, May 17, 2016

Leetcode 18: 4 Sum

May 17, 2016


Introduction


Julia likes to write some code after she reads the blog:


Write her own practice using C#. 

Will come back. 

January 31, 2017

Study C++ code first. 

Code review study here

Follow up


Dec. 29, 2017

It feels good to read the blog written 18 months ago. At that time, I was shy and do not write too much how I feel to learn 4 sum algorithm. At that time, I do not know that I can use Leetcode 18 discussion to find all the solutions. It is so interesting to know the person who I was 18 months ago. The code I liked at that time usually is searched from Google.

I like to review the blog written by TenosDolt, and then copy and paste the analysis of Leetcode 18: 4 Sum in Chinese here.

算法 2: 
O(n2)的算法,和前面相当,都是先对数组排序。

哈希map预处理

我们先枚举出所有二个数的和存放在哈希map中,其中map的key对应的是二个数的和,因为多对元素求和可能是相同的值,故哈希map的value是一个链表(下面的代码中用数组代替),链表每个节点存的是这两个数在数组的下标;这个预处理的时间复杂度是O(n2

枚举第一个和第二个元素方法

接着和算法1类似,枚举第一个和第二个元素,假设分别为v1, v2, 然后在哈希map中查找和为target - v1 - v2的所有二元对(在对应的链表中),查找的时间为O(1),为了保证不重复计算,我们只保留两个数下标都大于 V2 的二元对(其实我们在前面3sum问题中所求得的三个数在排序后的数组中下标都是递增的),即使是这样也有可能重复。

Example study

比如排好序后数组为[-9, -4, -2, 0, 2, 4, 4],target = 0,当第一个和第二个元素分别是-4,-2时,我们要得到和为0 -(-2) -(-4) = 6的二元对,这样的二元对有两个, 都是(2,4),且他们在数组中的下标都大于-4和-2,如果都加入结果,则(-4,-2,2,4)会出现两次,因此在加入二元对时,要判断是否和已经加入的二元对重复. 

由于过早二元对之前数组已经排过序,所以两个元素都相同的二元对可以保证在链表中是相邻的,链表不会出现(2,4)->(1,5)->(2,4)的情况,因此只要判断新加入的二元对和上一个加入的二元对是否重复即可.

因为同一个链表中的二元对两个元素的和都是相同的,因此只要二元对的一个元素不同,则这个二元对就不同。我们可以认为哈希map中key对应的链表长度为常数,那么算法总的复杂度为O(n2).

Also, I will study the code written in Java and then write a C# version. First, let me save the java code in a gist first. 

One thing I like to read the blog written by TenosDolt is that he recommended a blog related to K sum algorithm in general.

No comments:

Post a Comment