package main

import (
	"sort"
)

func twoSum(nums []int, target int) [][]int {
	n := len(nums)
	l, r := 0, n-1
	res := make([][]int, 0)
	for l < r {
		ln, rn := nums[l], nums[r]
		sum := ln + rn
		if sum < target {
			for ; l < r && nums[l] == ln; l++ {
			}
		} else if sum > target {
			for ; l < r && nums[r] == rn; r-- {
			}
		} else {
			res = append(res, []int{ln, rn})
			for ; l < r && nums[l] == ln; l++ {
			}
		}
	}
	return res
}

func threeSum(nums []int) [][]int {
	if len(nums) < 3 {
		return [][]int{}
	}
	sort.Ints(nums)
	res := make([][]int, 0)
	for a := 0; a < len(nums)-2; a++ {
		if a > 0 && nums[a] == nums[a-1] {
			continue
		}
		// the same as twoSum: target -> -nums[a], nums -> nums[a+1:]
		// one or more or none solutions
		b, c := a+1, len(nums)-1
		for b < c {
			nb, nc := nums[b], nums[c]
			sum := nums[a] + nb + nc
			if sum < 0 {
				b++
			} else if sum > 0 {
				c--
			} else {
				res = append(res, []int{nums[a], nb, nc})
				for ; b < c && nums[b] == nb; b++ {
				}
				for ; b < c && nums[c] == nc; c-- {
				}
			}
		}
	}
	return res
}

/* func main() {
	a1 := []int{-1, 0, 1, 2, -1, -4}
	fmt.Println(threeSum(a1))

	a2 := []int{-1, 0, -4}
	fmt.Println(threeSum(a2))

	a3 := []int{0, 0, 0}
	fmt.Println(threeSum(a3))
} */