三数之和

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

题面

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 协议》，转载必须注明作者和本文链接