三数之和

哈希与双指针两种思路实现,关键在去重

题面

n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。

哈希

  • 充分复用排序,哈希计数信息
  • 三数之和,三数要么不同,要么有相同
  • 计数区分可否相同,哈希裁定第三数是否存在,排序缩小其范围
func threeSum(nums []int) [][]int {
    sort.Ints(nums)
    length := len(nums)
    if length < 3 || nums[length-1] < 0 || nums[0] > 0 {
        return nil
    }
    ans := [][]int{}
    hash := make(map[int]int)
    for _, v := range nums {
        hash[v]++
    }

    for i:=0;i<length;i += hash[nums[i]] {
        for l:= i+hash[nums[i]];l<length && nums[l] < -nums[i]-nums[l];l +=hash[nums[l]]{ // 三数不同
            if _, ok := hash[-nums[i]-nums[l]];ok{
                ans = append(ans, []int{nums[i],nums[l],-nums[i]-nums[l]})
            }
        }
        if hash[nums[i]] > 1 {  // 三数存在相同
            if _,ok :=  hash[-nums[i]*2];ok {
                if nums[i] == 0 && hash[0] < 3 { continue }  
                ans = append(ans, []int{nums[i],nums[i], -nums[i]*2})
            }
        }
    }
    return ans
}

双指针

  • 排序+循环遍历去重
    func threeSum(nums []int) [][]int {
      sort.Ints(nums)
      length := len(nums)
      if length < 3 || nums[length-1] < 0 || nums[0] > 0 {
          return nil
      }
      ans := [][]int{}
      for i:=0;i<length;i++ {
          if i==0 || nums[i] != nums[i-1] { // 非重复项为首
              for l,r:= i+1,length-1;l<r;{
                  if nums[l]+nums[r] == -nums[i] { // 左右边界同时收缩
                      ans = append(ans,[]int{nums[i],nums[l],nums[r]})
                      for l<r && nums[l] == nums[l+1]{l++}  // 去重
                      for l<r && nums[r] == nums[r-1]{r--}  // 去重
                      l++
                      r--
                  }else if nums[l]+nums[r] < -nums[i] { // 左边界收缩
                      l++
                  }else{ // 右边界收缩
                      r--
                  }
              }
          }
      }    
      return ans
    }

二合一

  • 化为两数之和,哈希计数跳跃
  • 维护解空间的有序性,化繁为简,相同或不同
    func threeSum(nums []int) [][]int {
      sort.Ints(nums)
      length := len(nums)
      if length < 3 || nums[length-1] < 0 || nums[0] > 0 {
          return nil
      }
      ans := [][]int{}
      hash := make(map[int]int)
      for _, v := range nums {
          hash[v]++
      }
      for i:=0;i<length;i+=hash[nums[i]] {
          for l,r:= i+hash[nums[i]],length-1;l<r;{
              if nums[l]+nums[r] == -nums[i] { // 左右边界同时收缩
                  ans = append(ans,[]int{nums[i],nums[l],nums[r]})
                  l +=hash[nums[l]]
                  r -=hash[nums[r]]
              }else if nums[l]+nums[r] < -nums[i] { // 左边界收缩
                  l +=hash[nums[l]]
              }else{ // 右边界收缩
                  r -=hash[nums[r]]
              }
          }
          if hash[nums[i]] > 1 {  // 存在相同元素
              if _, ok := hash[-nums[i]*2];ok && nums[i] <= -nums[i]*2{ // 保证有序去重
                  if nums[i] == 0 && hash[0] < 3 {continue}  // 排除特例
                  ans = append(ans, []int{nums[i],nums[i],-nums[i]*2})
              }
          }
      }    
      return ans
    }
本作品采用《CC 协议》,转载必须注明作者和本文链接
pardon110
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!
开发者 @ 社科大
文章
125
粉丝
16
喜欢
92
收藏
46
排名:99
访问:4.7 万
私信
所有博文