Problem
Given an integer array nums, return all the unique triplets
[nums[i], nums[j], nums[k]] such that:
i != ji != kj != knums[i] + nums[j] + nums[k] === 0
The solution set must not contain duplicate triplets.
Mind Map
- Sort the array first.
- Fix one number and search for the remaining two values.
- Use two pointers:
- Left pointer moves forward.
- Right pointer moves backward.
- If the total is too small, move left.
- If the total is too large, move right.
- Skip duplicate values to avoid repeated triplets.
Brute Force Approach
Check every possible combination of three numbers and store only unique
triplets whose sum is equal to 0.
function threeSum(nums: number[]): number[][] {
const result: number[][] = [];
const seen = new Set<string>();
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
for (let k = j + 1; k < nums.length; k++) {
if (nums[i] + nums[j] + nums[k] === 0) {
const triplet = [nums[i], nums[j], nums[k]].sort((a, b) => a - b);
const key = triplet.join(",");
if (!seen.has(key)) {
seen.add(key);
result.push(triplet);
}
}
}
}
}
return result;
}