3Sum

1. Problem Description

Given an array nums containing n integers, determine whether there are three elements a, b, and c such that a + b + c = 0. Find all unique triplets whose sum is 0.

2. Approach

1. Approach 1
   • Because the values rather than the indices are needed, sort the array first
   • Fix one value, then use two pointers for the other two values and move them toward the center
   • Finally, deduplicate the results
     • Deduplicate with a map
     • Deduplicate while traversing

3. Implementation

3.1. Sort + Two Pointers (Map Deduplication)

func threeSum(nums []int) [][]int {
    insertSort(nums)
    res := make([][]int, 0)
    set := make(map[string]bool, 0)
    for i := 0; i < len(nums)-2; i++ {
        one := nums[i]
        target := -one

        left := i+1
        right := len(nums)-1
        for left < right {
            two := nums[left]
            three := nums[right]
            s := sum(two, three)
            if s == target {
                current := []int{one, two, three}
                if !set[getKey(current)]{
                    res = append(res, current)  
                    set[getKey(current)] = true  
                }
                left++
                right--
            }else if s < target {
                left++
            }else {
                right--
            }
        }
    }

    return res
}

func sum(nums ...int) int {
    s := 0
    for _, num := range nums {
        s += num
    }
    return s
}

func getKey(current []int) string {
    key := fmt.Sprintf("%v_%v_%v", current[0], current[1], current[2])
    return key
}


func insertSort(nums []int) {
	for i := 1; i < len(nums); i++ {
		toBeInserted := nums[i]
		position := i
		for position > 0 && nums[position-1] > toBeInserted {
			nums[position] = nums[position-1]
			position--
		}
		nums[position] = toBeInserted
	}
}

3.2. Sort + Two Pointers (Traversal Deduplication)

func threeSum2(num []int) [][]int {
	if len(num) < 3 {
		return nil
	}

	insertSort(num)
	res := make([][]int, 0)

	for i := 0; i < len(num)-2; i++ {
		j := i + 1
		k := len(num) - 1
		target := -num[i]
		for j < k {
			if num[j]+num[k] > target {
				k--
			} else if num[j]+num[k] < target {
				j++
			} else {
				res = append(res, []int{num[i], num[j], num[k]})
				// Deduplicate
				for j+1 < k && num[j+1] == num[j] {
					j++
				}
				// Deduplicate
				for k-1 > j && num[k-1] == num[k] {
					k--
				}
				j++
				k--
			}
		}
		// Deduplicate
		for i+1 < len(num)-2 && num[i+1] == num[i] {
			i++
		}
	}

	return res
}

func insertSort(nums []int) {
	for i := 1; i < len(nums); i++ {
		toBeInserted := nums[i]
		position := i
		for position > 0 && nums[position-1] > toBeInserted {
			nums[position] = nums[position-1]
			position--
		}
		nums[position] = toBeInserted
	}
}

4. References

• Illustrated Algorithm: 15. 3Sum - LeetCode
• Sort + Two Pointers, Explained Line by Line - 3Sum - LeetCode