Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 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]
]
func threeSum(nums []int) [][]int {
if len(nums)==0{
return make([][]int,0)
}
sort.Ints(nums)
var index int=-1
if nums[0]==0&&nums[0]==nums[len(nums)-1]{
if len(nums)<3{
return make([][]int,0)
}else if len(nums)>=3{
return append(make([][]int,0), nums[0:3])
}
}
for t:=0;t<len(nums);t++{
if nums[t]>=0&&index==-1 {
index=t
break
}
}
if index==-1||index==len(nums){
return make([][]int,0)
}
slice:=make([][]int,0)
if index+2<len(nums)&&nums[index+2]==0{
slice=append(slice, nums[index:index+3])
}
for i:=0;i<index;i++{
if i!=0&&nums[i]==nums[i-1]{
continue
}
for j:=len(nums)-1;j>=index;j--{
if j!=len(nums)-1&&nums[j]==nums[j+1]{
continue
}
tmp:=nums[i]+nums[j]
if tmp>0 {
if 0-tmp<nums[i]{
continue
}
if getvalue(nums[i+1:index],0-tmp){
var arr[]int=[]int{nums[i],nums[j],0-tmp}
slice=append(slice,arr)
continue
}
}else{
if 0-tmp >nums[j]{
continue
}
if getvalue(nums[index:j],0-tmp){
var arr[]int=[]int{nums[i],nums[j],0-tmp}
slice=append(slice,arr)
continue
}
}
}
}
return slice
}
func getvalue(num[]int ,value int)bool{
if len(num)==0{
return false
}
if len(num)==1{
return num[0]==value
}
var mid=len(num)/2
if value<num[mid]{
return getvalue(num[0:mid],value)
}else if value>num[mid]{
return getvalue(num[mid+1:len(num)],value)
}else {
return true
}
}