8.19三数之和 - WisperDin/blog GitHub Wiki

描述

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

思路

对于这种数组任意元素n数之和的问题，若使用暴力解法，需要多次遍历才能够解出问题，所以关键在于减少遍历的成本。

在本题中，

1. 先对输入的数组进行排序
2. 将value存入map中，使用两层遍历，针对三数之和的前两个数，剩下的值再从map中判断是否存在该元素
3. 对于消除重复的元组，通过
   • 在两层遍历前都加上判断，若接下来遍历到的值与上一次一样，则继续
   • 在判断得到map中指定元素存在时，保证从元素比本次遍历往后位置的元素中找（保证总是往后查找三元组中的元素）
   • 在判断得到map中指定元素存在且符合要求时，break跳出，不需要相同的结果了

实现

func threeSum(nums []int) [][]int {
    if len(nums)<=2{
        return [][]int{}
    }
    
    targetSum := 0
    valMap := make(map[int][]int)
    
    //sort
    sort.Ints(nums)
    fmt.Println(nums)
    
    //get value map
    for i,v := range nums {
        if _,ok := valMap[v];!ok{
            valMap[v] = []int{i}
            continue
        }
        valMap[v] = append(valMap[v],i)
	}
    
    ans := [][]int{}
    
    for i:=0 ; i< len(nums)-2 ; i++ {
        //remove duplicate
        if i!=0 && nums[i]==nums[i-1]{
            continue
        }
        for j:=i+1; j< len(nums);j++ {
            //remove duplicate
            if j!= i+1 && nums[j]==nums[j-1]{
                continue
            }
            
            remain := targetSum - nums[i] - nums[j]
            
            if _,ok := valMap[remain];!ok{
                continue
            }
            
            for _,numsIndex := range valMap[remain] {
                if numsIndex <= j {
                    continue
                }
                
                ans = append(ans,[]int{nums[i],nums[j],nums[numsIndex]})
                //remove duplicate
                break
            }
            continue
        }
    }
    
    return ans
}

总结

对n数之和的题目，可以采取思路：

• 将数组value或可能以某种函数关系的value 用map保存，因为从哈希表中读取元素只有O(1)的时间复杂度
• 对排序后的元素，考察每个元素时，对剩下元素用双指针，一根指向最小元素，一根指向最大元素进行收缩