15. 3Sum

Intuition

The key insight is to use a two-pointer approach after sorting the array. By sorting first, we can efficiently find all unique triplets that sum to zero while avoiding duplicates.

Approach

1. Sort the array to enable the two-pointer technique
2. Use three pointers: start, mid, and last
3. For each start position:
   • Use mid and last pointers to find pairs that sum to -nums[start]
   • Move mid forward if sum is too small
   • Move last backward if sum is too large
4. Use a map to store unique triplets
5. Convert the map keys back to the required return format

Complexity

• Time complexity: O(n²)
• Space complexity: O(n)

Keywords

• Sorting
• Hash Map

Code

func threeSum(nums []int) [][]int {
    mp := make(map[[3]int]bool)
    ret := make([][]int, 0)
    sort.Ints(nums)

    for start, mid, last := 0, 1, len(nums) - 1; start < last; {
        for mid < last {
            if nums[start] + nums[mid] + nums[last] == 0 {
                mp[[3]int{nums[start], nums[mid], nums[last]}] = true
                mid += 1
                last -= 1
            } else {
                if nums[start] + nums[mid] + nums[last] < 0 {
                    mid += 1
                } else {
                    last -= 1
                }
            }
        }
        if mid >= last {
            start += 1
            mid = start + 1
            last = len(nums) - 1
        }
    }

    for key := range mp {
        ret = append(ret, []int{key[0], key[1], key[2]})
    }
    return ret
}