设为首页 加入收藏

TOP

三数之和的golang实现
2018-12-15 22:08:57 】 浏览:94
Tags:三数 之和 golang 实现

给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。

注意:答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4],

满足要求的三元组集合为:
[
  [-1, 0, 1],
  [-1, -1, 2]
]
我们来看一下图:

我们先对数组排序,得到如下图的结果

 

我们要计算a+b+c=0,先对数组循环得到a,然后b就是a的索引+1的值,c是len(nums)-1的值。

 

如果a+b+c<0的是时候,说明太小了,那b就往右挪一下

反之,如果a+b+c>0,那么说明太大了,c就往左挪一下

核心代码:
func threeSum2(nums []int) [][]int {
    
 
			
000">//
先对数组排序 sort.Ints(nums) result := [][]int{} for i := 0; i < len(nums)-1; i++ { if i > 0 && nums[i] == nums[i-1] { continue } j := i + 1 z := len(nums) - 1 for z > j { b := nums[j] c := nums[z] if nums[i]+b+c > 0 { z-- } else if nums[i]+b+c < 0 { j++ } else { item := []int{nums[i], b, c} result = append(result, item) for j < z && nums[j] == nums[j+1] { j++ } for j < z && nums[z] == nums[z-1] { z-- } j++ z-- } } } return result }

去重技巧:

  • 在循环一开始的时候,就判断当前位的值是否跟上一位一样,一样的话就跳过
  • 在把符合条件的值存进数组的时候,判断b的下一位是不是和b一样,判断c的下一位是不是和c一样,一样的话那就直接跳过

编程开发网
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇验证二叉搜索树的golang实现 下一篇Qt显示Linux desktop natificatio..

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(217) }