package main

// 排序+双指针法
import (
	"fmt"
	"sort"
)

func main() {
	var nums []int

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

	nums = []int{3, 0, -2, -1, 1, 2}
	fmt.Println(threeSum(nums))
}

func threeSum(nums []int) [][]int {
	var ret = [][]int{}
	sort.Ints(nums)
	for i := 0; i < len(nums); i++ {
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		var j, k = i + 1, len(nums) - 1
		for j < k {
			var num = nums[i] + nums[j] + nums[k]
			if num == 0 {
				ret = append(ret, []int{nums[i], nums[j], nums[k]})
				for j < k {
					j++
					if nums[j] != nums[j-1] {
						break
					}
				}

				for k > j {
					k--
					if nums[k] != nums[k+1] {
						break
					}
				}
			} else {
				if num > 0 {
					k--
				}
				if num < 0 {
					j++
				}

				// 添加了这里的优化，反而时间多了一点，但是内存少了许多
				//if num > 0 {
				//	for k > j {
				//		k--
				//		if nums[k] != nums[k+1] {
				//			break
				//		}
				//	}
				//}
				//if num < 0 {
				//	for j < k {
				//		j++
				//		if nums[j] != nums[j-1] {
				//			break
				//		}
				//	}
				//}
			}
		}
	}
	return ret
}