题目链接

https://leetcode-cn.com/problems/3sum/

解法思路

先对数组进行排序，排序完之后对数组进行遍历，每遍历一个元素设置左右两个指针，左指针指向当前元素的下一个元素，右指针指向数组最后一个元素，然后对当前元素，左指针指向元素，右指针指向元素进行相加，如果相加的和大于0，则将右指针左移（减少总和），如果小于0，则将左指针右移（增大总和），如果等于0，则当前元素、左指针元素、右指针元素满足题目要求。

但是一个元素可能有多种组合满足题目要求，如：[-2, 0, 1, 1, 1, 1, 2]，遍历到2时，满足=0的结果集有[-2, 1, 1]和[-2, 0, 2]有两个解，但是按我们以上的逻辑只是移动左右指针求和，[-2, 1, 1]这个答案会出现两次，这样子答案就会出现重复值，所以我们要做一层过滤，如果左指针元素和左指针右边元素值相等（即nums[left] == nums[left + n]），则将左指针持续右移，同理，右指针元素如果和右指针左边元素相等（即nums[right] == nums[right - 1]），则将右指针持续左移。

解法代码

  2. func threeSum(nums []int) [][]int {
  3.     length := len(nums)
  5.     var result [][]int
  7.     if length < 3 {
  8.         return result
  9.     }
  11.     // 排序
  12.     quickSort(nums, 0, length-1)
  14.     var left, right int
  16.     for i := 0; i < length-1; i++ {
  18.         // 相同组合的跳过
  19.         if i > 0 && nums[i] == nums[i-1] {
  20.             continue
  21.         }
  23.         // 左右指针所在位置
  24.         left, right = i+1, length-1
  26.         for left < right {
  28.             sum := nums[i] + nums[left] + nums[right]
  30.             if sum > 0 {
  31.                 right--
  32.             } else if sum < 0 {
  33.                 left++
  34.             } else {
  35.                 item := []int{nums[i], nums[left], nums[right]}
  36.                 result = append(result, item)
  37.                 for left < right && nums[left] == nums[left + 1] {
  38.                     left++
  39.                 }
  40.                 if left < right && nums[right] == nums[right - 1] {
  41.                     right--
  42.                 }
  43.                 left++
  44.                 right--
  45.             }
  46.         }
  47.     }
  49.     return result
  50. }
  52. func quickSort(sortArray []int, left, right int) {
  53.     if left < right {
  54.         pos := partition(sortArray, left, right)
  55.         quickSort(sortArray, left, pos-1)
  56.         quickSort(sortArray, pos+1, right)
  57.     }
  58. }
  60. func partition(sortArray []int, left, right int) int {
  61.     key := sortArray[right]
  62.     i := left - 1
  64.     for j := left; j < right; j++ {
  65.         if sortArray[j] <= key {
  66.             i++
  67.             sortArray[i], sortArray[j] = sortArray[j], sortArray[i]
  68.         }
  69.     }
  71.     sortArray[i+1], sortArray[right] = sortArray[right], sortArray[i+1]
  73.     return i + 1
  74. }