首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Array - 15. 3Sum

Array - 15. 3Sum

作者头像
ppxai
发布2020-09-23 17:47:29
2270
发布2020-09-23 17:47:29
举报
文章被收录于专栏:皮皮星球皮皮星球

15. 3Sum

Given an array nums of n integers, are there elements abc in nums 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.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

思路:

找出数组中三数和的所有组合,解决思路是首先做一个排序,然后对于每一位元素,去找出剩下数组中找出两个数和当前元素三个数和为0就可以,主要要留意重复元素就不用了计算在内。

代码:

go:

func threeSum(nums []int) [][]int {

    var res = make([][]int, 0)
    sort.Ints(nums)
    for i := 0; i < len(nums) - 2; i++ {
        if i > 0 && nums[i] == nums[i-1] {
            continue;
        }
        
        low := i + 1
        high := len(nums) - 1
        sum := 0 - nums[i]
        for low < high {
            if nums[low] + nums[high] == sum {
                res = append(res, []int{nums[i], nums[low], nums[high]})
                // 去重
                for low < high && nums[low] == nums[low+1] {
                    low++
                }
                for low < high && nums[high] == nums[high-1] {
                    high--
                }
                // 下一种
                low++
                high--
            } else if  nums[low] + nums[high] < sum {
                low++
            } else {
                high--
            }
        }
    } 
    
    return res
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2019年12月25日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档