Question
Given an array of integers, find all unique triplets that sum up to 0. The solution must not contain duplicate triplets.
Example
Input:
nums = [4, 3, 2, 2, 0, 0, 4, 1, -1, -2, -2]
Output:
[[-2, -2, 4] [-2, -1, 3] [-2, 0, 2] [-1, 0, 1]]
Explanation: Only unique triplets are included.
Input: nums = [0, 0, 0, 0]
Output: [[0, 0, 0]]
My Notes
- Sort the array first to make it easier to avoid duplicates.
- Use a fixed pointer (i), and two pointers (j and k) for scanning.
- If you find a triplet, skip over duplicates using inner while loops.
-
Time complexity:
O(n²), space:O(1)(excluding output).
package main
import (
"fmt"
"sort"
)
func main() {
result := threeSum([]int{4, 3, 2, 2, 0, 0, 4, 1, -1, -2, -2})
fmt.Println(result)
}
func threeSum(nums []int) [][]int {
sort.Ints(nums)
result := make([][]int, 0)
for i := 0; i < len(nums)-2; i++ {
if i > 0 && nums[i] == nums[i-1] {
continue
}
j, k := i+1, len(nums)-1
target := -nums[i]
for j < k {
sum := nums[j] + nums[k]
if sum == target {
result = append(result, []int{nums[i], nums[j], nums[k]})
j++
k--
for j < k && nums[j] == nums[j-1] {
j++
}
for j < k && nums[k] == nums[k+1] {
k--
}
} else if sum < target {
j++
} else {
k--
}
}
}
return result
}