3Sum

Given an integer array nums, return all unique triplets [a, b, c] such that a + b + c == 0. Each triplet should be in non-decreasing order, and the overall order of triplets does not matter.

A naive triple loop is O(n^3). Sorting plus two pointers reduces it to O(n^2).

Function signature

func ThreeSum(nums []int) [][]int

Inputs / outputs

• nums: input slice of integers.
• Return: slice of unique triplets that sum to zero.

Example

nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Constraints

• 0 <= len(nums) <= 3000
• -100_000 <= nums[i] <= 100_000

Core idea (near-solution)

Sort the array. For each index i, solve a 2-sum problem on the subarray to the right using two pointers.

Invariants:

• The array is sorted, so moving pointers changes the sum monotonically.
• Duplicates must be skipped to avoid repeated triplets.

Algorithm (step-by-step)

1. Sort nums.
2. For each i from 0 to len(nums)-3:
   • Skip i if it is a duplicate of i-1.
   • Set l = i+1, r = len(nums)-1.
   • While l < r:
     • Compute sum = nums[i] + nums[l] + nums[r].
     • If sum == 0, record the triplet, then move l and r past duplicates.
     • If sum < 0, increment l.
     • If sum > 0, decrement r.
3. Return the collected triplets.

Correctness sketch

• Each step moves at least one pointer, shrinking the remaining search space.
• The invariant ensures elements outside the active window are already handled correctly.
• When pointers meet or cross, all candidates have been considered.

Trace (hand walkthrough)

Example input:
nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Walk:
- sort -> [-4,-1,-1,0,1,2]
- i=1 (-1), l=2 (-1), r=5 (2): sum=0 -> add [-1,-1,2]
- move l=3 (0), r=4 (1): sum=0 -> add [-1,0,1]
- other i values give no new triples

Pitfalls to avoid

• Forgetting to skip duplicates at i, l, and r.
• Returning triplets in an unsorted order (keep the sorted array order).

Complexity

• Time: O(n^2) after sorting.
• Extra space: O(1) beyond output (sorting may take O(log n) stack).

Implementation notes (Go)

• Use sort.Ints on nums.
• To compare in tests, sort each triplet or normalize ordering.