# Leetcode 15 3Sum

Datetime:2016-08-23 01:20:21         Topic: LeetCode          Share        Original >>

Given an array S of  n integers, are there elements  abc in  S such that  abc = 0? Find all unique triplets in the array which gives the sum of zero.

Note: 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]
]Solution:此题的关键在于如何避免duplicate triplets. 此处解决方法为只考虑首次出现的值，以[-4,-1,-1,-1,0,1,2]为例，循环第一次到-1时，所有跟－1有关的triplets [-1,0,1],[-1,-1,2]已经出现,则第二次循环到－1的时候，忽略这个subloop一直到发现下一个非－1的值,此处为0.```
```public class Solution {
public IList<IList<int>> ThreeSum(int[] nums) {
List<int> newList = nums.ToList();
List<IList<int>> returnList = new List<IList<int>>();
newList.Sort();
for(int i = 0; i < newList.Count() -2; i++)
{
if((i == 0)||( (newList[i] != newList[i - 1])))
{
int low = i + 1;
int high = nums.Length - 1;
int sum = 0 - newList[i];
while(low < high)
{
if(newList[low]+newList[high] == sum)
{
returnList.Add(new List<int>() { newList[i?], newList[low], newList[high] });
while ((low < high) && (newList[low] == newList[low + 1])) low++;//duplicate
while ((low < high) && (newList[high] == newList[high - 1])) high--;//duplicate
low++;
high--;
}
else if(newList[low]+newList[high] < sum)
{
low++;
}
else
{
high--;
}
}
}
}
return returnList;

}
}
```