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(n3), 不知道没有更好的算法,请不吝赐教。
同样的用了一个Dictionary 集合帮助做防止重复的验证。