题目
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. 大意为：给定一个整型数组，其中存在abc三个整数相加等于0，请找出他们，并且要求不重复出现
例子
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]
思路
最简单粗暴的方法就是三层遍历，一个一个去搜寻；很明显，一般这种都是会超时的。 我们可以先对他进行从小到大排序，然后从第一位开始固定，在后面的元素中寻找和为固定元素值得反数，使用两个指针，头尾往中间移动；遍历直到倒数第2个； 接下来是关于去重，由于已经排好序，所以固定的元素如果与他前面一位相同的，则可以跳过；在同一个固定值下，搜索到的结果的头指针如果和上一个结果相同，则跳过；
func threeSum(nums []int) [][]int {
if len(nums)==0 {
return nil
}
length := len(nums)-1
var retInts [][]int
retInts = make([][]int,0,0)
//sort
QuitSort(nums,0,length)
for i,v := range nums{
if i==0&&v>0{
return nil
}
if i>=length-1{
break
}
target := -v
h,e := i+1,length
mark := false
var recordPre int
if i!=0&&nums[i]==nums[i-1]{
continue
}
for h<e {
for h<e && (nums[h]+nums[e])>target{
e--
}
for h<e && (nums[h]+nums[e])<target{
h++
}
if (nums[h]+nums[e])==target&&h<e{
if !mark {
mark = true
}else{
if recordPre==nums[h]{
e--
h++
continue
}
}
retInt := make([]int,0,0)
retInt = append(retInt,v,nums[h],nums[e])
retInts = append(retInts,retInt)
recordPre = nums[h]
e--
h++
}
}
}
return retInts
}
func Quitsort(nums []int,start int,end int) int{
sential := nums[start]
for start<end{
for start<end&&nums[end]>=sential { end--}
nums[start]=nums[end]
for start<end&&nums[start]<=sential{ start++ }
nums[end]=nums[start]
}
nums[end]=sential
return end
}
func QuitSort(nums []int,start int,end int){
if start<end{
mid := Quitsort(nums,start,end)
QuitSort(nums,start,mid-1)
QuitSort(nums,mid+1,end)
}
}
