GO题解 | #数组中相加和为0的三元组#

go解题答案

• 时间复杂度O(n^2)

• 思路概括：先排序，降低难度，去重只判断和上一个是否相等即可

• 思路核心：
  1、因为要找全部的不重复解，所以
  (1、每组解的索引都是递增的，即索引abc, a<b b<c
  (2、固定a指针，去求bc指针，固定b指针求c,如果bc一起找，则去重很麻烦

  import "sort"
  func threeSum(nums []int) [][]int {
    count:=len(nums)
    if count<3{
        return [][]int{}
    }
  
    sort.Ints(nums) // 排序后简化的问题，可以使用滑动窗口
    ans := make([][]int, 0)
    // 寻找 -a=b+c
    for a:=0;a<count;a++{
        if a>0 && (nums[a]==nums[a-1]){ //去掉重复a，因为排过序，所以只跟上一个比
            continue
        }
        target:=(-nums[a])
        c:=count-1 //如果c=b+1可能会越界
        for b:=a+1;b<count;b++{ // 固定b找c
            if (b>a+1) && nums[b]==nums[b-1]{ //去掉重复b
                continue
            }
            for b<c && (nums[b]+ nums[c]>target) {
                c--
            }
            if b==c {
                break
            }
            if nums[b]+ nums[c]==target{
                ans=append(ans,[]int{nums[a],nums[b],nums[c]})
            }
  
        }
    }
    return ans
  }

  如果有帮助请点个赞哦， 更多文章请看我的博客

  题主背景

• 从业8年——超级内卷500Q技术经理——目前专注go和微服务架构