前言
改年号了，还来水一水
正文
问题来源
本问题来自leetcode上的15题。
问题描述
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
示例
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
分析：
func threeSum(nums []int) [][]int {
sort.Ints(nums)
ret := make([][]int, 0)
l := len(nums)
lt := l - 2
var k, j int
var a, b, c int//临时变量，尝试优化
for i := 0; (i < lt) && (nums[i]<=0); i++ {
k = i + 1
j = l - 1
if (i > 0) && (nums[i] == nums[i-1]) {
continue
}
for k < j {
a, b, c = nums[i], nums[k], nums[j]
if a + b + c < 0 {
k++
} else if a + b + c > 0 {
j--
} else {
subRet := append([]int{}, a, b, c)
ret = append(ret, subRet)
for (k < j) && (b == nums[k+1]) { //去重
k++
}
for (k < j) && (c == nums[j-1]) { //去重
j--
}
k++
j--
}
}
}
return ret
}
提交之后居然只打败百分之九十一的对手。 主要差别在于去重的地方
func threeSum(nums []int) [][]int {
sort.Ints(nums)
l := len(nums)
var result [][]int
for i := 0; i < l - 1 && nums[i] <= 0; i++ {
if i > 0 && nums[i] == nums[i - 1] {
continue
}
j := i + 1
k := l - 1
target := 0 - nums[i]
for ; j < k; {
sum := nums[j] + nums[k]
if sum == target {
result = append(result, []int{nums[i], nums[j], nums[k]})
j++
for j < k && nums[j-1] == nums[j] {
j++
}
k--
for j < k && nums[k+1] == nums[k] {
k--
}
} else if sum > target {
k--
for j < k && nums[k+1] == nums[k] {
k--
}
} else {
j++
for j < k && nums[j-1] == nums[j] {
j++
}
}
}
}
return result
}
总结：
这题主要在于思考如何降低算法的开销
结语
不要懒，多看多写。
