三数之和

1. 题目描述

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

2. 思路

1. 思路一
   • 由于需要找的是value而不是index，所以可以先进行排序
   • 接着固定一个value，其他两个用双指针往中间靠拢
   • 最后需要去重
     • map去重
     • 遍历去重

3. 实现

3.1. 排序后双指针（map去重）

func threeSum(nums []int) [][]int {
    insertSort(nums)
    res := make([][]int, 0)
    set := make(map[string]bool, 0)
    for i := 0; i < len(nums)-2; i++ {
        one := nums[i]
        target := -one

        left := i+1
        right := len(nums)-1
        for left < right {
            two := nums[left]
            three := nums[right]
            s := sum(two, three)
            if s == target {
                current := []int{one, two, three}
                if !set[getKey(current)]{
                    res = append(res, current)  
                    set[getKey(current)] = true  
                }
                left++
                right--
            }else if s < target {
                left++
            }else {
                right--
            }
        }
    }

    return res
}

func sum(nums ...int) int {
    s := 0
    for _, num := range nums {
        s += num
    }
    return s
}

func getKey(current []int) string {
    key := fmt.Sprintf("%v_%v_%v", current[0], current[1], current[2])
    return key
}


func insertSort(nums []int) {
	for i := 1; i < len(nums); i++ {
		toBeInserted := nums[i]
		position := i
		for position > 0 && nums[position-1] > toBeInserted {
			nums[position] = nums[position-1]
			position--
		}
		nums[position] = toBeInserted
	}
}

3.2. 排序后双指针（遍历去重）

func threeSum2(num []int) [][]int {
	if len(num) < 3 {
		return nil
	}

	insertSort(num)
	res := make([][]int, 0)

	for i := 0; i < len(num)-2; i++ {
		j := i + 1
		k := len(num) - 1
		target := -num[i]
		for j < k {
			if num[j]+num[k] > target {
				k--
			} else if num[j]+num[k] < target {
				j++
			} else {
				res = append(res, []int{num[i], num[j], num[k]})
				//去重
				for j+1 < k && num[j+1] == num[j] {
					j++
				}
				//去重
				for k-1 > j && num[k-1] == num[k] {
					k--
				}
				j++
				k--
			}
		}
		//去重
		for i+1 < len(num)-2 && num[i+1] == num[i] {
			i++
		}
	}

	return res
}

func insertSort(nums []int) {
	for i := 1; i < len(nums); i++ {
		toBeInserted := nums[i]
		position := i
		for position > 0 && nums[position-1] > toBeInserted {
			nums[position] = nums[position-1]
			position--
		}
		nums[position] = toBeInserted
	}
}

4. 参考

• 画解算法：15. 三数之和 - 三数之和 - 力扣（LeetCode）
• 排序 + 双指针，逐行解释 - 三数之和 - 力扣（LeetCode）