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


  • 0
    M

    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
    }
    

Log in to reply
 

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