三数之和

题目：
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

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

• 例1:

输入：nums = [-1, 0, 1, 2, -1, -4]
输出：[[-1, -1, 2], [-1, 0, 1]]

• 例2:

输入：nums = []
输出：[]

• 例3:

输入：nums = [0]
输出：[]

---

答案

• 暴力破解法

func threeNumSum(_ nums: [Int]) -> [[Int]] {
  /// 使用有序数组 + 集合的唯一性处理去重问题
  let soredArray = nums.sorted()
  var result = Set<[Int]>()
  for i in 0 ..< (soredArray.count - 2) {
    let sum = -soredArray[i]
    for j in (i + 1) ..< (soredArray.count - 1) {
      for k in (j + 1) ..< soredArray.count {
        if (soredArray[j] + soredArray[k]) == sum {
            result.insert([soredArray[i], soredArray[j], soredArray[k]])
          }
        }
      }
    }
  return Array(result)
}

---

• 双指针法

func threeNumSum(_ nums: [Int]) -> [[Int]] {
  /// 处理异常情况
  guard !nums.isEmpty && (nums.count > 2) else { return [] }
  /// 1. 首先对数据进行排序
  let sortedArray = nums.sorted()
  /// 2. 初始化左右指针
  var result = [[Int]](),
        left = 0,
        right = sortedArray.count - 1
  for i in 0 ..< sortedArray.count - 2 {
    if (i > 0) && (sortedArray[i] == sortedArray[i - 1]) {
      continue
    }
    left = i + 1
    let sum = -sortedArray[i]
    while left < right {
      let res = sortedArray[left] + sortedArray[right]
      if sum == res {
        result.append([sortedArray[i], sortedArray[left], sortedArray[right]])
        /// 去重
        /// 左指针向右边移动
        while (left < right) {
          // 不管前后相不相等，left 都要往前走
          left += 1
          if (nums[left - 1] != nums[left]) {
              break
              }
          }
          /// 右指针向左边移动
          while (left < right) {
              // 不管前后相不相等，right 都要往后走
              right -= 1
              if (nums[right + 1] != nums[right]) {
                  break
                 }
              }
          } else if sum < res {
              right -= 1
          } else {
              left += 1
          }
        }
    }
  return result
}