LeetCode Online Judge 题目C# 练习 - 4SUM

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

• Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
• The solution set must not contain duplicate quadruplets.

    For example, given array S = {1 0 -1 0 -2 2}, and target = 0.

    A solution set is:
    (-1,  0, 0, 1)
    (-2, -1, 1, 2)
    (-2,  0, 0, 2)

 1         public static List<List<int>> fourSum(int[] S, int target)
 2         {
 3             List<List<int>> ret = new List<List<int>>();
 4             if(S.Length < 4)
 5                 return ret;
 6 
 7             Array.Sort(S);
 8             string str;
 9             Dictionary<string, bool> map = new Dictionary<string,bool>();
10 
11             for(int a = 0; a <= S.Length - 4; a++)
12             {
13                 for(int b = a + 1; b <= S.Length - 3; b++)
14                 {
15                     int c = b+1;
16                     int d = S.Length - 1;
17                     while(c < d)
18                     {
19                         if(S[a] + S[b] + S[c] + S[d] == target)
20                         {
21                             str = S[a].ToString() + S[b].ToString() + S[b].ToString() + S[c].ToString();
22                             if(map.ContainsKey(str))
23                             {
24                                 c++;
25                                 d--;
26                             }
27                             else
28                             {
29                                 List<int> quadruplet = new List<int> { S[a], S[b], S[c], S[d]};
30                                 map.Add(str, true);
31                                 ret.Add(quadruplet);
32                                 c++;
33                                 d--;
34                             }
35                         }
36                         else if (S[a] + S[b] + S[c] + S[d] < target)
37                             c++;
38                         else
39                             d--;
40                     }
41                 }
42             }
43 
44             return ret;
45         }

代码分析:

　　这一题比前面3SUM和3SUM Cloeset多了一个指针，但是原理还是相同，先排列数组，然后BRUTE FROCE。这使整个算法的时间复杂度为O(n³), 不知道没有更好的算法，请不吝赐教。

　　同样的用了一个Dictionary 集合帮助做防止重复的验证。