3Sum

Medium

The problem

Given a list of numbers, find every group of three numbers (taken from three different positions) that add up to 0. Return the groups as a list of lists. The same group of values must not appear twice in your answer, and the order of the groups does not matter. Return an empty list if there are none.

Example 1
Input: nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]
-1 + -1 + 2 = 0 and -1 + 0 + 1 = 0. The value -1 appears twice in the list, but the group [-1, 0, 1] is only reported once.
Example 2
Input: nums = [0, 1, 1]
Output: []
The only group is 0 + 1 + 1 = 2, which is not 0.
Example 3
Input: nums = [0, 0, 0]
Output: [[0, 0, 0]]
0 + 0 + 0 = 0.

Limits

3 ≤ nums.length ≤ 3,000
-100,000 ≤ nums[i] ≤ 100,000

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

Fix one number; the rest is the problem you just solved. How do you avoid duplicate triplets?

The idea

Sort. For each i (skipping equal neighbours) run two pointers on the rest looking for −nums[i]; after a hit, skip equal values on both sides.

Target: O(n²) time, O(1) extra space

Go function shape

func threeSum(nums []int) [][]int

Reference solution

Tested with go test. Try it yourself first, then compare.

// ThreeSum: unique triplets summing to zero.
// Fix one number, then run the opposite-ends scan on the rest; skip duplicates.
func ThreeSum(nums []int) [][]int {
	sort.Ints(nums)
	out := [][]int{}
	for i := 0; i < len(nums)-2; i++ {
		if nums[i] > 0 {
			break // everything after is positive too
		}
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		left, right := i+1, len(nums)-1
		for left < right {
			sum := nums[i] + nums[left] + nums[right]
			if sum < 0 {
				left++
			} else if sum > 0 {
				right--
			} else {
				out = append(out, []int{nums[i], nums[left], nums[right]})
				left++
				right--
				for left < right && nums[left] == nums[left-1] {
					left++
				}
			}
		}
	}
	return out
}

Read the lesson: Two Pointers