Problem
Given an integer array nums, return all the unique triplets[nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. The solution must not contain duplicate triplets.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
nums = [-1,0,1,2,-1,-4] Output
[[-1,-1,2],[-1,0,1]] Solution
This solution first sorts the array, allowing the Two Pointer technique to be used efficiently.Each element is treated as the first element of a triplet. Two pointers are then used to search for the remaining two elements whose sum equals the negative of the current element.
If the current sum is smaller than zero, the left pointer is moved forward to increase the sum. If the sum is greater than zero, the right pointer is moved backward to decrease the sum.
When a valid triplet is found, it is added to the result, and both pointers are moved while skipping duplicate values.
To avoid duplicate triplets, duplicate starting elements are skipped before processing each iteration, and duplicate values are also skipped after finding a valid triplet.
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
// Skip duplicate first elements.
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
result.add(Arrays.asList(
nums[i], nums[left], nums[right]
));
left++;
right--;
// Skip duplicate second elements.
while (left < right && nums[left] == nums[left - 1]) {
left++;
}
// Skip duplicate third elements.
while (left < right && nums[right] == nums[right + 1]) {
right--;
}
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
Complexity
The array is sorted first, which takesO(n log n) time. After sorting, each element is processed as the first element of a triplet, and the remaining portion of the array is scanned using two pointers. This results in an overall time complexity of O(nĀ²).
Apart from the space required to store the output, the algorithm uses only a few variables during processing, resulting in an extra space complexity of
O(1).