Function threeSum

three_sum_15/solution.go:5–48

(nums []int)

import "sort"

func threeSum(nums []int) [][]int {
	triplets := make([][]int, 0)
	sort.Ints(nums)

	if len(nums) < 3 {
		return triplets
	}

	// pick a number, then solve the two sum problem in the space in front of it
	for i := 0; i < len(nums); i++ {
		// skip duplicates of the starting number if we've seen it in the past
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}

		// determine what is needed from two sum
		need := 0 - nums[i]
		start := i + 1
		end := len(nums) - 1
		for start < end {
			// if we've found what we need
			if nums[start]+nums[end] == need {
				triplets = append(triplets, []int{nums[i], nums[start], nums[end]})

				// Choose to skip duplicates on one end or the other (start or end)
				// In my first answer below, I skipped duplicates from start, for example.
				// We need to continue to search in the space in between start and end
				// for more sums that equal need. So, we need to move one end forward
				// and skip duplicates in order to satisfy the 'unique' requirement of
				// the problem.
				end--
				for start < end && nums[end] == nums[end+1] {
					end--
				}
			} else if nums[start]+nums[end] > need {
				end--
			} else {
				start++
			}
		}
	}

	return triplets
}

func threeSum0(nums []int) [][]int {
	triplets := make([][]int, 0)