Leetcode 18: 4 Sum

May 17, 2016

Introduction

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

http://www.cnblogs.com/TenosDoIt/p/3649607.html

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(n²)的算法，和前面相当，都是先对数组排序。

哈希map预处理

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

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

接着和算法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(n²).

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.