3sum.go

import (
	"sort"
	"fmt"
)

func threeSum(nums []int) [][]int {
	// count elements
	var counts = make(map[int]int)
	for _, n := range nums {
		counts[n] = counts[n] + 1
	}

	// remove too much duplicated elements
	nums = []int{}
	for key, value := range counts {
		if 1 == value {
			nums = append(nums, key)
		} else {
			nums = append(append(nums, key, key))
		}
	}
	sort.Ints(nums)

	// compute answer
	var cache = make(map[string]int)
	var result = make([][]int, 0)
	for i := 0; i < len(nums); i += 1 {
		for k := i + 1; k < len(nums); k += 1 {
			v0 := nums[i]
			v1 := nums[k]
			v2 := -(v0 + v1)
			if v2 < v1 {
				continue
			}

			var duplicatedCount = 0
			if v0 == v2 {
				duplicatedCount += 1
			}
			if v1 == v2 {
				duplicatedCount += 1
			}
			if duplicatedCount < counts[v2] {
				newAnswer := []int{v0, v1, v2}
				newAnswerCacheKey := fmt.Sprintf("%#v", newAnswer)
				if 0 < cache[newAnswerCacheKey] {
					continue
				}
				result = append(result, newAnswer)
				cache[newAnswerCacheKey] = 1
			}
		}
	}
	return result
}