Given an array nums of n integers, are there elements a,b,c in nums such that a+b+c = 0?
Find all unique triplets in the array which gives the sum of zero.
Note : 過不了 TimeLimit 還需要修改
#region LeetCode 15 3Sum
/*
* Given an array nums of n integers, are there elements a,b,c in nums such that a+b+c = 0?
* Find all unique triplets in the array which gives the sum of zero.
*
* Notice that the solution set must not contain duplicate triplets.
*
* Input : nums = [ -1, 0, 1, 2, -1, 4]
* Output : [[-1,-1,2], [-1,1,0]]
*
* Input : nums = []
* Output : []
*
* Input : nums = [0]
* Output : []
*
* Input : nums = [0,0,0]
* Output : [0,0,0]
*
* Input : nums = [-4, -2, 1, -5, -4, -4, 4, -2, 0, 4, 0, -2, 3, 1, -5, 0]
* Output : [[-5,1,-4], [-4,0,4] [-4,1,3], [-2,-2,4], [-2,1,1], [0,0,0]]
*
* Input : nums = [10,-2,-12,3,-15,-12,2,-11,3,-12,9,12,0,-5,-4,-2,-7,-15,7,4,-5,-14,-15,-15,-4,10,9,-6,7,1,12,-6,14,-15,12,14,10,0,10,-10,3,4,-12,10,7,-9,-7,-15,-8,-15,-4,2,9,-4,3,-10,13,-3,-1,5,5,-4,-15,4,-11,4,-4,6,-11,-9,12,7,11,7,2,-5,13,10,-5,-10,3,7,0,-3,10,-12,2,9,-8,8,-9,13,12,13,-6,8,3,5,-9,7,12,10,-8,0,2,1,10,-7,-3,-10,-10,7,4,5,-11,-8,0,-2,-14,8,13,-8,-2,10,13]
* Output : [[-15,1,14],[-15,2,13],[-15,3,12],[-15,4,11],[-15,5,10],[-15,6,9],[-15,7,8],[-14,0,14],[-14,1,13],[-14,2,12],[-14,3,11],[-14,4,10],[-14,5,9],[-14,6,8],[-14,7,7],[-12,-2,14],[-12,-1,13],[-12,0,12],[-12,1,11],[-12,2,10],[-12,3,9],[-12,4,8],[-12,5,7],[-11,-3,14],[-11,-2,13],[-11,-1,12],[-11,0,11],[-11,1,10],[-11,2,9],[-11,3,8],[-11,4,7],[-11,5,6],[-10,-4,14],[-10,-3,13],[-10,-2,12],[-10,-1,11],[-10,0,10],[-10,1,9],[-10,2,8],[-10,3,7],[-10,4,6],[-10,5,5],[-9,-5,14],[-9,-4,13],[-9,-3,12],[-9,-2,11],[-9,-1,10],[-9,0,9],[-9,1,8],[-9,2,7],[-9,3,6],[-9,4,5],[-8,-6,14],[-8,-5,13],[-8,-4,12],[-8,-3,11],[-8,-2,10],[-8,-1,9],[-8,0,8],[-8,1,7],[-8,2,6],[-8,3,5],[-8,4,4],[-7,-7,14],[-7,-6,13],[-7,-5,12],[-7,-4,11],[-7,-3,10],[-7,-2,9],[-7,-1,8],[-7,0,7],[-7,1,6],[-7,2,5],[-7,3,4],[-6,-6,12],[-6,-5,11],[-6,-4,10],[-6,-3,9],[-6,-2,8],[-6,-1,7],[-6,0,6],[-6,1,5],[-6,2,4],[-6,3,3],[-5,-5,10],[-5,-4,9],[-5,-3,8],[-5,-2,7],[-5,-1,6],[-5,0,5],[-5,1,4],[-5,2,3],[-4,-4,8],[-4,-3,7],[-4,-2,6],[-4,-1,5],[-4,0,4],[-4,1,3],[-4,2,2],[-3,-3,6],[-3,-2,5],[-3,-1,4],[-3,0,3],[-3,1,2],[-2,-2,4],[-2,-1,3],[-2,0,2],[-2,1,1],[-1,0,1],[0,0,0]]
*/
public IList<IList<int>> LeetCode_15(int[] nums)
{
IList<IList<int>> ans = new List<IList<int>>();
List<int> Negative = new List<int>();
List<int> Zero = new List<int>();
List<int> Positive = new List<int>();
if(nums.Length <= 1)
{
return ans;
}
Array.Sort(nums);
for (int i = 0; i < nums.Length; i++)
{
if (nums[i] > 0)
Positive.Add(nums[i]);
else if (nums[i] == 0)
Zero.Add(nums[i]);
else
Negative.Add(nums[i]);
}
if (Zero.Count >= 3)
ans.Add(new List<int> { Zero[0], Zero[1], Zero[2] });
if (Zero.Count > 0 && Positive.Count > 0 && Negative.Count > 0)
{
//1P+1N
for (int i = 0; i < Positive.Count; i++)
{
for (int j = 0; j < Negative.Count; j++)
{
if (Positive[i] + Negative[j] == 0)
{
ans.Add(new List<int>() { Negative[j], Zero[0], Positive[i] });
}
}
}
}
if (Positive.Count >= 1 && Negative.Count >= 2)
{
//1+2
for (int i = 0; i < Positive.Count; i++)
for (int j = 0; j < Negative.Count; j++)
for (int k = (j + 1); k < Negative.Count; k++)
{
if (Positive[i] + Negative[j] + Negative[k] == 0)
{
ans.Add(new List<int>() { Negative[j], Negative[k], Positive[i] });
}
}
}
if (Positive.Count >= 2 && Negative.Count >= 1)
{
//2+1
for (int i = 0; i < Positive.Count; i++)
for (int j = (i + 1); j < Positive.Count; j++)
for (int k = 0; k < Negative.Count; k++)
{
if (Positive[i] + Positive[j] + Negative[k] == 0)
{
ans.Add(new List<int>() { Negative[k], Positive[i], Positive[j] });
}
}
}
//刪除重複
for (int i = 0; i < ans.Count; i++)
for (int j = ans.Count - 1; j > i; j--)
{
if(ans[i].ElementAt(0) == ans[j].ElementAt(0) && ans[i].ElementAt(1) == ans[j].ElementAt(1) && ans[i].ElementAt(2) == ans[j].ElementAt(2))
{
ans.RemoveAt(j);
}
}
return ans;
}
#endregion