3Sum
Problem
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.
Examples
Example 1
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Constraints
- •
3 <= nums.length <= 3000 - •
-10^5 <= nums[i] <= 10^5
Hints
Hint 1
The brute force checks every triplet directly — O(n^3), plus real care needed to avoid duplicate triplets in the output.
Hint 2
Sorting first (O(n log n), a small one-time cost) turns 'find two numbers that sum to a target' into a problem two pointers can solve in a single O(n) pass, since sorted order lets you reason about which pointer to move.
Hint 3
After sorting, fix the first number and reduce the rest to a Two Sum-style search on the remaining sorted subarray using two pointers — skip over repeated values at every level to avoid duplicate triplets.
Solutions
public List<List<Integer>> threeSumBruteForce(int[] nums) {
Set<List<Integer>> result = new HashSet<>();
Arrays.sort(nums); // sort only to make de-duplication straightforward, not required for correctness
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
for (int k = j + 1; k < nums.length; k++) {
if (nums[i] + nums[j] + nums[k] == 0) {
result.add(List.of(nums[i], nums[j], nums[k]));
}
}
}
}
return new ArrayList<>(result);
}Time: O(n^3) · Space: O(n) for the result set