# Golang, ~n^2+n worst case, no sort, no deduplication, O(n^2), beats 50%

• I haven't seen this solution in the top posts so I thought I'd share it.
The basic strategy for 3Sum is the same as everywhere: for each (i, j) pair find a k such that
k = -(i+j)

The no-dedupe strategy is:

• get unique numbers using a map (number -> duplicates of that number)
• find all pairs of numbers, but on each pair the left has to be smaller than the right, unless there are 2 of them
• when you find the third number, it has to be larger than the other two, or it can be equal to exactly one of them (if there are 2 of them in the list), or exactly two of them (if there are 3 of them in the list)

This strategy guarantees no need for deduping, but there are quite a few no-op iterations that could be avoided with different strategies. It did beat 50% of other submissions.

``````func threeSum(nums []int) [][]int {
if len(nums) <= 2 {
return make([][]int, 0)
}
var (
m   = make(map[int]int, 0)
res = make([][]int, 0)
)
for _, n := range nums {
m[n]++
}
for i := range m {
for j := range m {
if i > j || (i == j && m[i] == 1) {
continue
}
k := -(i + j)
if k < i || k < j {
continue
}
if n, ok := m[k]; ok {
if (k == i && n == 1) || (k == j && n == 1) || (i == j && j == k && n == 2) {
continue
}
res = append(res, []int{i, j, k})
}
}
}
return res
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.