LeetCode Online Judge 题目C# 练习 - 3SUM
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
- Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
- The solution set must not contain duplicate triplets.
For example, given array S = {-1 0 1 2 -1 -4},
A solution set is:
(-1, 0, 1)
(-1, -1, 2)
16 /// <summary>
17 /// Find Triplet that S[a] + S[b] + S[c] = 0
18 /// </summary>
19 /// <param name="S">input array</param>
20 /// <returns>HasSet of Triplet which ensure no duplicate</returns>
21 public static HashSet<List<int>> threeSum(int[] S)
22 {
23 HashSet<Triplet> ret = new HashSet<Triplet>();
24 if(S.Length < 3) //if array length less than 3, return a empty HastSet<Triplet>
25 return ret;
26
27 Array.Sort(S);
28
29 for (int a = 0; a <= S.Length - 3; a++)
30 {
31 int b = a + 1;
32 int c = S.Length - 1;
33 while (b < c)
34 {
35 if (S[a] + S[b] + S[c] == 0)
36 {
37 List<int> triplet = new List<int> { S[a], S[b], S[c] };
38 ret.Add(triplet);
39 b++;
40 c--;
41 }
42 else if (S[a] + S[b] + S[c] > 0)
43 c--;
44 else
45 b++;
46 }
47 }
48
49 return ret;
50 }代码分析：
代码的算法应该算比较简单，我总结这种题目为指针题（不知道这种说法正不正确，请各位指正）。
我设了3个指针（当然你这里不是真正意义上的指针，只是3个在数组上游走的index）: a, b 和 c。a 从 0 到S.Length - 3 循环， b和c分别从a+1, S.Length -1 往中间走，碰到 S[a] + S[b] + S[c] == 0 插入到HashSet中， 如果 S[a] + S[b] + S[c] > 0, c--，S[a] + S[b] + S[c] < 0, b++, 知道b >= c 的时候跳出内循环。
因为题目要求triplet不能有重复，所有我一开始想到用HashSet这个.NET提供的集合（Collectino）来帮助消除重复的元素。因为HashSet在每次做Add()插入的时候都会去检查一下集合里面有没有相同的元素，如果有，则不执行插入，如果没有，则执行插入。
问题来了，就算我使用了HashSet，我的ret里面还是有重复的triplet组合。经过一番研究，知道原来HashSet在比较里面是否存在元素的时候，会调用元素的GetHashCode(), 而且因为每次插入我们都创建一个新的List<int>实例，所以就算List<int>里面的组合是相同，GetHashCode()方法返回的值都是不同的（因为是不同的实例）。所以，我们需要自己建一个类，继承List<int>这个集合，然后overrideGetHashCode()方法，以及Equal(object obj)方法，因为当GetHashCode()返回值相同以后，HashSet会再去调用Equal(object obj)方法来确认这两个元素确实相同（Hash Function不能避免有collision吧）。而最原始的System.Object 类的Equal()方法实现是看这两个实例是否指向同一个地址，所以我们也必须重写他。（两个不同的实例永远不会指向同一地址吧，我也不知道微软有没有重写List<T>的Equal()方法，希望大牛能指点一下）
所以一下代码我创建了一个继承List<int>的Triplet类，然后重写了以上两个方法。
1 public class Triplet : List<int>
2 {
3 public override int GetHashCode()
4 {
5 return (this[0].ToString() + this[1].ToString() + this[2].ToString()).GetHashCode();
6 }
7 public override bool Equals(object obj)
8 {
9 var other = obj as Triplet;
10 if(other == null)
11 return false;
12 return this[0] == other[0] && this[1] == other[1] && this[2] == other[2];
13 }
14 }
15
16 /// <summary>
17 /// Find Triplet that S[a] + S[b] + S[c] = 0
18 /// </summary>
19 /// <param name="S">input array</param>
20 /// <returns>HasSet of Triplet which ensure no duplicate</returns>
21 public static HashSet<Triplet> threeSum(int[] S)
22 {
23 HashSet<Triplet> ret = new HashSet<Triplet>();
24 if(S.Length < 3) //if array length less than 3, return a empty HastSet<Triplet>
25 return ret;
26
27 Array.Sort(S); //Sort the array
28
29 for (int a = 0; a <= S.Length - 3; a++)
30 {
31 int b = a + 1;
32 int c = S.Length - 1;
33 while (b < c)
34 {
35 if (S[a] + S[b] + S[c] == 0)
36 {
37 Triplet triplet = new Triplet { S[a], S[b], S[c] };
38 ret.Add(triplet);
39 b++;
40 c--;
41 }
42 else if (S[a] + S[b] + S[c] > 0)
43 c--;
44 else
45 b++;
46 }
47 }
48
49 return ret;
50 }这样就实现没有duplicates这个要求了。
当然了，我们可以不用HashSet这个集合也可以做到没有重复。
1 public static List<List<int>> threeSumNoSet(int[] S)
2 {
3 List<List<int>> ret = new List<List<int>>();
4 if(S.Length < 3)
5 return ret;
6 Array.Sort(S);
7 string str;
8 Dictionary<string, bool> map = new Dictionary<string, bool>();
9
10 for (int a = 0; a <= S.Length - 3; a++)
11 {
12 int b = a + 1;
13 int c = S.Length - 1;
14 while (b < c)
15 {
16 if (S[a] + S[b] + S[c] == 0)
17 {
18 str = S[a].ToString() + S[b].ToString() + S[c].ToString();
19 if (map.ContainsKey(str))
20 {
21 b++;
22 c--;
23 }
24 else
25 {
26 List<int> triplet = new List<int> { S[a], S[b], S[c] };
27 map.Add(str, true);
28 ret.Add(triplet);
29 b++;
30 c--;
31 }
32 }
33 else if (S[a] + S[b] + S[c] > 0)
34 c--;
35 else
36 b++;
37 }
38 }
39
40 return ret;
41 }代码分析：
在上面的代码，我们使用的Dictionary<key, value>这个泛型集合帮组我们检查重复，而且建了一个string = S[a].ToString() + S[b].ToString() + S[c].ToString() 作为Dictionary的key。因为我们的数组 S 已经是排列过的(Sorted),所以不肯定不会出现{-1,0,1}, {-1,1,0}这种应视为重复的情况。
这题就做到这里了，在做题过程中，学习很多自己以前没有留意到的东西，比如如果泛型HashSet<>里面是个reference type, 它会如何比较元素是否相等。