目录
数组中相加和为0的三元组
访问量:1508

一、简介

给出一个有n个元素的数组S,S中是否有元素a,b,c满足a+b+c=0?找出数组S中所有满足条件的三元组。

注意:

三元组(a、b、c)中的元素必须按非降序排列。(即a≤b≤c)

解集中不能包含重复的三元组。

例如,给定的数组 S = {-10 0 10 20 -10 -40},解集为(-10, -10, 20),(-10, 0, 10) 


二、实现

分析:本题本质三数之和,因为要非降序排列,多了一个排序。

/**
 *
 * @param num int整型一维数组
 * @return int整型二维数组
 */
func threeSum( num []int ) [][]int {
   // write code here
   if len(num) < 3 {
      return nil
   }
   
   // 对数据进行 排序
   sort.Ints(num)
   var (
      left  = 0
      right = len(num) - 1
   )

   unqMap := make(map[string]bool)
   rs := make([][]int, 0)
   for left < right {
      if num[left] > 0 {
         break
      }


      for j := right; j > left ; j -- {
         // 判断 left ~ right之间,是否存在一个数字,满足 三元组
         seekVal := 0 - num[left] - num[j]
         for i:= left +1; i < j; i++ {
            if num[i] != seekVal {
               continue
            }
            
            if num[i] > seekVal {
                break
            }

            // 因为要去重,满足之前,要判断是否有重复
            key := fmt.Sprintf("%d_%d_%d", num[left], num[i], num[j])
            if unqMap[key] {
               continue
            }

            // 存在三元组
            rs = append(rs, []int{num[left], num[i], num[j]})
            unqMap[key] = true
         }
      }

      left ++
      for left < right && num[left] == num[left -1] {
         left ++
      }
   }

   return rs
}



题目来源:牛客