package main

import (
	"fmt"
	"sort"
)

func fourSum(nums []int, target int) (res [][]int) {
	// 用三数之和的思路试试
	sort.Ints(nums)
	left , leftMid , rightMid , right, n := 2 , 0 , 1, len(nums)-1, len(nums)
	for leftMid < n - 3  {
		rightMid = leftMid + 1
		for rightMid < n - 2 {
			left ,right = rightMid + 1 , n - 1
			// 移动左右指针
 			for left < right {
				v := nums[left] + nums[leftMid] + nums[rightMid] + nums[right]
				if v == target {
					res = append(res, []int{nums[left],nums[leftMid],nums[rightMid],nums[right]})
					for right > rightMid && nums[right-1] == nums[right] {
						right --
					}
				}
				if v < target  {
					left ++
				}else {
					right --
				}
			}
			// 移动右value到新值
			rv := nums[rightMid]
			for rightMid < n - 2 && rv == nums[rightMid] {
				rightMid ++
			}
		}
		// 移动左value到新值
		lv := nums[leftMid]
		for leftMid < n - 3 && lv== nums[leftMid] {
			leftMid ++
		}
	}
	return res
}

func main() {
	fmt.Println(fourSum([]int{0,0,0,0,0,0,0,0,0},0))
}