题解 | #不重复打印排序数组中相加和为给定值的所有三元组#

//反正用fmt.Scan就不追求什么速度了

package Chenxuyuandaimamianshi_ACM_mode_

import (
	"fmt"
	"sort"
)

func main() {
	var (
		N, K, n int
	)
	fmt.Scanln(&N, &K)
	Arr := []int{}
	nMap := map[int]int{}

	//读取数据，并且剔除重复的
	for i := 0; i < N; i++ {
		fmt.Scan(&n)
		//剔除重复数据
		if _, ok := nMap[n]; !ok {
			nMap[n]++
			Arr = append(Arr, n)
		}
	}
	//排序
	sort.Ints(Arr)
	res := sum3(Arr, K)
	for _, nums := range res {
		fmt.Printf("%d %d %d\n", nums[0], nums[1], nums[2])
	}

}

// 不考虑重复的情况，即提前对数据去重
func sum3(arr []int, target int) [][]int {
	res := [][]int{}
	if len(arr) < 3 {
		return res
	}
	for i := 0; i < len(arr)-2; i++ {
		temp := sum2(arr[i+1:], target-arr[i])
		if len(temp) != 0 {
			for j := range temp {
				cur := []int{arr[i]}
				cur = append(cur, temp[j]...)
				res = append(res, cur)
			}
		}
	}
	return res

}

func sum2(arr []int, target int) [][]int {
	res := [][]int{}
	l, r := 0, len(arr)-1
	for l < r {
		if arr[l]+arr[r] == target {
			res = append(res, []int{arr[l], arr[r]})
		}
		if arr[l]+arr[r] < target {
			l++
		} else {
			r--
		}
	}
	return res
}