# LeetCode 15. 3Sum

3Sum.

My solution here is to use a hash table to achieve a O(n2) performance. Basically you can just brute force two number, and check if the last number exists for checking the hash table. There is a less space intensive solution (but harder to understand.) I use it in the 3Sum Closest problem.

```public class Solution {
public IList<IList<int>> ThreeSum(int[] nums) {
Dictionary<int, int> dict = new Dictionary<int, int>();
IList<IList<int>>  ret = new List<IList<int>>();
if (nums.Length == 0) return ret;
foreach(int i in nums){
if(dict.ContainsKey(i)) dict[i] += 1;
else dict[i] = 1;
}
Array.Sort(nums);
for(int i = 0; i < nums.Length && nums[i] <= 0; i++){ if(i > 0 && nums[i] == nums[i-1]) continue;
for (int j = i+1; j < nums.Length && nums[j] + nums[i] <= 0; j++){ if(j > i+1 && nums[j] == nums[j-1]) continue;
int k = 0 - nums[j] - nums[i];
if (k < nums[j]) continue; int count = 1; if (k == nums[j]) count += 1; if (k == nums[i]) count += 1; if (dict.ContainsKey(k) && dict[k] >= count){
IList<int> tuple = new List<int>();
tuple.Add(nums[i]);
tuple.Add(nums[j]);
tuple.Add(k);
ret.Add(tuple);
}
}
}
return ret;
}
}
```