golang力扣leetcode 15.三数之和

package main
import (
  "sort"
)
//二层循环+hash暴力解
func threeSum1(nums []int) [][]int {
  result := make([][]int, 0)
  //特判
  if len(nums) <= 2 || len(nums) == 3 && nums[0]+nums[1]+nums[2] != 0 {
    return result
  }
  //从小到达排序
  sort.Ints(nums)
  mp := make(map[int]int)
  for k, v := range nums {
    mp[v] = k
  }
  for i := 0; i <= len(nums)-1-2; i++ {
    //避免重复
    if i != 0 && nums[i] == nums[i-1] {
      continue
    }
    //剪枝
    if nums[i] > 0 {
      break
    }
    for j := i + 1; j <= len(nums)-1-1; j++ {
      //避免重复
      if j != i+1 && nums[j] == nums[j-1] {
        continue
      }
      //用哈希表判断是否存在这个数，并且其索引大于第二个数，如果小于，说明后面不可能有合为0的条件了
      if k, ok := mp[0-(nums[i]+nums[j])]; ok {
        if k > j {
          result = append(result, []int{nums[i], nums[j], 0 - (nums[i] + nums[j])})
        } else {
          break
        }
      }
    }
  }
  return result
}
//双指针
func threeSum2(nums []int) [][]int {
  result := make([][]int, 0)
  if len(nums) <= 2 || len(nums) == 3 && nums[0]+nums[1]+nums[2] != 0 {
    return result
  }
  sort.Ints(nums)
  for i := 0; i <= len(nums)-1-2; i++ {
    if i != 0 && nums[i] == nums[i-1] {
      continue
    }
    if nums[i] > 0 {
      break
    }
    //left为第二个数，right为第三个数
    left, right := i+1, len(nums)-1
    for left < right {
      //如果三数之和大于0，说明第三个数太大了--->前面排过序了，下面小于0同理
      if nums[i]+nums[left]+nums[right] > 0 {
        right--
      } else if nums[i]+nums[left]+nums[right] < 0 {
        left++
      } else {
        //等于零存起来，并且去重
        result = append(result, []int{nums[i], nums[left], nums[right]})
        for left+1 < len(nums) && nums[left] == nums[left+1] {
          left++
        }
        for right-1 >= 0 && nums[right] == nums[right-1] {
          right--
        }
        //去完重，这些数字已经存过了，所有移到下一个判断位去
        left++
        right--
      }
    }
  }
  return result
}