牛客网: BM54
题目: 数组中所有不重复的满足三数之和等于0的数,非递减形式。
思路: 数组不小于3。不重复非递减,需先排序。使用idx从0开始遍历到n-2, 如果出现num[idx]==num[idx-1]的情况,忽略继续下一个idx;令left = idx+1, right = n-1,双指针迎面而行,如果满足num[left]+num[right]=-num[idx],则获取一个满足条件的解;为避免重复,分别对left、right一边检测一边移动,注意边界条件left+1<right;如果num[left]+num[right]>-num[idx],则right--;否则left++。
代码:
// go
package main
import "sort"
// import "fmt"
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param num int整型一维数组
* @return int整型二维数组
*/
func threeSum( num []int ) [][]int {
// write code here
if len(num) < 3 {
return [][]int{}
}
sort.Ints(num)
res := [][]int{}
for idx := 0; idx < len(num) - 2; idx++ {
if idx > 0 && num[idx] == num[idx-1] {
continue
}
left := idx + 1
right := len(num) - 1
target := -num[idx]
for left < right {
if num[left] + num[right] == target {
res = append(res, []int{num[idx], num[left], num[right]})
for left + 1 < right && num[left] == num[left+1] {
left++
}
for right - 1 > right && num[right] == num[right-1] {
right--
}
left++
right--
} else if num[left] + num[right] > target {
right--
} else {
left++
}
}
}
return res
}