3Sum

1. 原文

   Given an array S of n integers, are there elements a, b, c in S 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.

   For example, given array S = [-1, 0, 1, 2, -1, -4],

   A solution set is:

    [
        [-1, 0, 1],
        [-1, -1, 2]
    ]
   

2. 翻译

   输入：一个整形数组

   输出：数组中所有和为\(0\)的三个数的集合，注：不能有同一组数据

3. 举例：

   输入： [-1, 0, 1, 2, -1, -4]

   输出：

    [
        [-1, 0, 1],
        [-1, -1, 2]
    ]
   

Solution

1. 先排序，再对数组中每个数据求 target - v的 2Sum，算法复杂度为\(O(n^2)\)

   对数组进行排序了之后可以有效地筛选出重复的数据

   在求2Sum的时候应保证结果不能有重复数据

    func threeSumTarget(nums []int, target int) [][]int {
        sumArray := make([][]int, 0)
        viMap := make(map[int]bool)
        //1.排序
        sort.Ints(nums)
        lenS := len(nums)
        for i, vv := range nums {
            if _, isExist := viMap[vv]; !isExist {
                if lenS > 3 && i < lenS-3 
                    && nums[i]+nums[i+1]+nums[i+2] > target 
                    || i > lenS-3 {
                    break
                }
                //2.求nums[i+1:]的twoSum， target 为target- nums[i]
                reNums := nums[i+1:]
                arr := twoSumTargetUnique(reNums, target-vv, -1, true)
                //3.追加结果
                for _, w := range arr {
                    sumArray = append(sumArray, []int{w[0], w[1], vv})
                }
                //4.对于重复值，直接跳过
                viMap[vv] = true
            }
   
        }
        return sumArray
    } 
   
    func twoSumTargetUnique(nums []int, 
                            target int,
                            excludeIndex int,
                            isSorted bool) [][]int {
        //基本校验
        if len(nums) < 2 {
            return sumSlice
        }
        viMap := make(map[int]int)
        sumSlice := make([][]int, 0)
        if !isSorted {
            sort.Ints(nums)
        }
        //相等的num字典，[值]重复次数
        epMap := make(map[int]int)
        //忽略掉可能的重复解法
        for i := 0; i < len(nums); i++ {
            //nums[i] 与 nums[i-1]重复，则加一次
            if i > 0 && nums[i] == nums[i-1] {
                epMap[nums[i]]++
            }
            _, isEq := epMap[nums[i]]
            //发现重复，或者等于需要排除的序号
            if i == excludeIndex || isEq {
                continue
            }
            //TwoSum经典算法
            if _, isExist := viMap[target-nums[i]]; isExist {
                sumSlice = append(sumSlice, []int{nums[i], target - nums[i]})
            } else {
                viMap[nums[i]] = i
            }
   
        }
   
        //恢复重复值，只算一次
        for v, r := range epMap {
            if r > 0 {
                if v+v == target {
                    sumSlice = append(sumSlice, []int{v, target - v})
                }
            }
        }
   
        return sumSlice
    }
   

2. 思路跟上面一样，只是在求 2Sum 的时候可以将数组第一个和最后一个元素相加，若等于 target 则取其值，若小于则增加左边游标，若大于则减少右边游标。 时间复杂度为\(O(n^2)\)

    func threeSumTarget(nums[] int, target int)[][]int{
        sort.Ints(nums)
        res :=make([][]int,0)
        for i:=0;i<len(nums) -2;i++{
            if i==0 || (i>0 && nums[i] != nums[i-1]){
                lo:=i+1
                hi:=len(nums)-1
                sum:=target - nums[i]
                for lo<hi{
                    if nums[lo] + nums[hi]  == sum{
                        res = append(res,[int]{nums[i],nums[lo],nums[hi]})
                        for lo<hi && nums[lo] == nums[lo +1]{
                            lo++
                        }
                        for lo<hi && nums[hi] == nums[hi-1]{
                            hi--
                        }
                        lo++
                        hi--
                    }else if nums[lo] + nums[hi]< sum{
                       lo++ 
                    }else{
                        hi--
                    }
                }
            }
        }
   
    }
   

总结

1. 在数组解中筛选重复解，可以考虑先对输入进行排序，然后重复输入就成了相邻值。
2. 将大的算法拆分成小的算法然后求解，比如3Sum可以拆分成2Sum+target。
3. 进行求 2Sum 可以考虑用两个指针来头尾相加以加快速度。