讨论/题目交流/三数之和/
三数之和

给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。

注意:答案中不可以包含重复的三元组。

给定数组 nums = [-1, 0, 1, 2, -1, -4],

满足要求的三元组集合为:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

展开讨论
Helen发起于 2020-04-07

func threeSum(nums []int) [][]int {

	result := [][]int{}

    var keyCountMap map[int]int /*创建集合 */
    keyCountMap = make(map[int]int,len(nums))

    for i := 0; i < len(nums); i++ {
        
        count, ok := keyCountMap [nums[i]] 
        if ok {
            keyCountMap[nums[i]]=count+1;
        }else{
             keyCountMap[nums[i]]=1;
        }
    }

    newNums := make([]int, 0, len(keyCountMap))

    for keyi := range keyCountMap {
        newNums = append(newNums, keyi)
        if keyCountMap[keyi] > 1{
            if keyi==0 {
                if(keyCountMap[keyi] > 2){
                    result = append(result, append([]int{}, 0, 0, 0)) 
                }
                continue
            }
            var remain= 0 - keyi * 2
            _, ok := keyCountMap [remain] 
            if ok {               
                result = append(result, append([]int{}, keyi, keyi, remain))
            }

        }
    }

    for i := 0; i < len(newNums); i++ {
        for j := i+1; j < len(newNums); j++ {
            var remain = 0-(newNums[i]+newNums[j])
            if remain == newNums[i] || remain == newNums[j] {
                continue
            }
            _, ok := keyCountMap [remain] 
            if ok {  

                var b1 bool = true

                for k:=0;k<len(result);k++ {
                    if(newNums[i] == result[k][0]){
                        if(newNums[j] == result[k][1] || remain == result[k][1]){
                            b1 = false
                            break
                        }

                    }else if newNums[j] == result[k][0] {
                        if(newNums[i] == result[k][1] || remain == result[k][1]){
                            b1 = false
                            break
                        }

                    }else if remain == result[k][0] {
                        if(newNums[i] == result[k][1] || newNums[j] == result[k][1]){
                            b1 = false
                            break
                        }
                    }
                    
                }

                if b1 {
                    result = append(result, append([]int{}, newNums[i], newNums[j], remain))
                }
                
            }
       
        }
    }
    
    return result;
}


展开全部 4 讨论