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

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

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

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

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

共 4 个回复
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
    const funcSeq = (a, b) => a - b;
    const sortedNums = nums.sort(funcSeq);
    const length = sortedNums.length;
    const result = [];
    for (let i = 0; i < length; i++) {
        let num = sortedNums[i];
        if (num > 0) break;
        if (num === sortedNums[i - 1]) continue;
        let lIndex = i + 1;
        let rIndex = length - 1;
        while (lIndex < rIndex) {
            let lNum = sortedNums[lIndex];
            let rNum = sortedNums[rIndex];
            if (lNum + num + rNum === 0) {
                result.push([lNum, num, rNum].sort(funcSeq).join(','));
                rIndex -= 1;
                lIndex += 1;
            } else if (lNum + num + rNum < 0) {
                lIndex += 1;
            } else if (lNum + num + rNum > 0) {
                rIndex -= 1
            }
        }
    }
    return Array.from(new Set(result)).map(str => str.split(','));
};
1

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;
}


var threeSum = function (nums) {
     let res = [];

    nums.sort((a, b) => a - b);

    if (nums.length >= 3) {
        
        for (let index = 0; index < nums.length - 1; index++) {
            let left = index + 1;
            let right = nums.length - 1;

            if (nums[index] === nums[index - 1]) {
                continue;
            }
            while (left < right) {
                let result = nums[index] + nums[left] + nums[right];
                
                if (result === 0) {
                    res.push([nums[left], nums[index], nums[right]]);
                    while(left < right && nums[left] === nums[left + 1]) { 
                        left++;
                    }
                    while(right > left && nums[right] === nums[right - 1]) { 
                        right--;
                    }
                    left++;
                    right--;
                } else if (result < 0) {
                    left++;
                } else if (result > 0) {
                    right--;
                }
            } 
        }
    }

    return res;
};