15. 3Sum
Intuition
!!! info The brute-force way to find all unique triplets that sum to 0 would involve checking all combinations of three numbers, which takes O(n³) time
To do better, we can:
- Sort the array to make it easier to detect and skip duplicates.
- Fix one element and then use a two-pointer approach to find the other two elements whose sum equals the negative of the fixed one.
This brings the time complexity down to O(n²) while avoiding duplicate triplets.
Code
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums); // Step 1: Sort the array
List<List<Integer>> triplets = new ArrayList<>();
for (int i = 0; i < nums.length; ++i) {
// Step 2: Skip duplicates for the first number
if (i > 0 && nums[i] == nums[i - 1]) continue;
// Step 3: Use two pointers to find remaining pair
int j = i + 1, k = nums.length - 1;
while (j < k) {
int sum = nums[i] + nums[j] + nums[k];
if (sum == 0) {
triplets.add(Arrays.asList(nums[i], nums[j], nums[k]));
k--;
// Step 4: Skip duplicates for third number
while (k > 0 && nums[k] == nums[k + 1]) k--;
} else if (sum > 0) {
k--;
while (k > 0 && nums[k] == nums[k + 1]) k--; // Skip duplicates
} else {
j++;
while (j < nums.length && nums[j] == nums[j - 1]) j++; // Skip duplicates
}
}
}
return triplets;
}