Description
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0?
Find all unique triplets in the array which gives the sum of zero.
Note: The solution set must not contain duplicate triplets.
For example, given array S = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
Analysis
Consider the brute force, iterate all the (a,b,c) and choose the valid results, the time complexity is O(n^3). There must be a faster method.
One idea is we divide the array to two groups: non-negative, negative, the valid result must contains 2 non-negative + 1 negative or 1 non-negative + 2 negative or 3 zeros. We just need to pick elements from two groups iteratively. The estimated time complexity is O(n^3).
A similar idea is using two pointers. Sort the array first, and then run through all indices of a possible first element of a triplet. For every possible first element, we use two points to go through the remaining part of the array. Also, we need to skip equal elements to avoid duplication. The time complexity is O(n^2).
Solution
Apprlach #1 (Two Pointers)
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> list = new ArrayList<List<Integer>>();
if (nums == null || nums.length < 3) return list;
Arrays.sort(nums);
for (int i = 0; i < nums.length-2; i++) {
// here is a refinement
// we only consider non-positive number as possible first element in a triplet
if (nums[i] > 0) break;
if (i==0 || (i>0 && nums[i]!=nums[i-1])) {
int low = i+1, high = nums.length-1, sum = -nums[i];
while (low < high) {
if (sum == nums[low] + nums[high]) {
list.add(Arrays.asList(nums[i], nums[low], nums[high]));
// remove duplication
while (low<high && nums[low]==nums[low+1]) low++;
while (low<high && nums[high]==nums[high-1]) high--;
low++;
high--;
} else if (sum > nums[low] + nums[high]) {
low++;
} else {
high--;
}
}
}
}
return list;
}
Complexity analysis
- Time complexity: O(n^2)
- Space complexity: O(1)
Comments powered by Talkyard.