一、简介

给出一个有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
}

题目来源：牛客