三数之和
哈希与双指针两种思路实现,关键在去重
题面#
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 协议》,转载必须注明作者和本文链接