Give you an array num containing n integers. Judge whether there are three elements a, b and c in num, so that a + b + c = 0? Please find all triples with sum 0 and no repetition.
Note: the answer cannot contain duplicate triples.
Example 1:
Input: num = [- 1,0,1,2, - 1, - 4]
Output: [- 1, - 1,2], [- 1,0,1]]
Example 2:
Input: num = []
Output: []
Example 3:
Input: num = [0]
Output: []
When I first saw this problem, the idea was to start working in three cycles directly, but the time complexity of this violent solution is the third power of n, and it will definitely timeout, so I chose to use sorting + double cycle + right pointer.
The code is as follows
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int n=nums.size();
sort(nums.begin(),nums.end());
int first=0,second=0,third=0;
vector<vector<int>> ans;
for(first=0;first<n;first++)
{
if(first>0 && nums[first]==nums[first-1])
{
continue;
}
int target = -nums[first];
int third = n-1;
for(second=first+1;second<n;second++)
{
if(second>first+1 && nums[second]==nums[second-1])
{
continue;
}
while(second<third && nums[second]+nums[third]>target)
{
third--;
}
if(third == second)
{
break;
}
if(nums[second]+nums[third]==target)
{
ans.push_back({nums[first],nums[second],nums[third]});
}
}
}
return ans;
}
};
The idea is to refer to the official solution of leetcode:
The title requires to find all triples with "no repetition" and sum of 000. This "no repetition" requirement makes it impossible for us to simply enumerate all triples with a triple loop. This is because in the worst case, all the elements in the array are 000, i.e
[0, 0, 0, 0, 0, ..., 0, 0, 0]
The sum of any triplet is 0. If we directly use triple loop to enumerate triples, we will get O(N3) triples that meet the requirements of the topic (where n is the length of the array). The time complexity is at least O(N3). After that, we also need to use the hash table for de duplication operation to get the final answer without duplicate triples, which consumes a lot of space. The time complexity and space complexity of this method are very high, so we should think about this problem in a different way.
What is the essence of "non repetition"? We keep the big framework of the triple cycle unchanged and only need to ensure that:
The elements enumerated in the second loop are not less than the elements enumerated in the current first loop; The elements enumerated by the third loop are not less than the elements enumerated by the current second loop.
In other words, the triples (a,b,c) we enumerated satisfy a ≤ b ≤ C, which ensures that only the order of (a,b,c) will be enumerated, while (b,a,c), (c,b,a) and so on will not, so as to reduce repetition. To achieve this, we can sort the elements in the array from small to large, and then use an ordinary triple loop to meet the above requirements.
At the same time, for each loop, the elements of two adjacent enumerations cannot be the same, otherwise it will cause repetition. For example, if the ordered array is
[0, 1, 2, 2, 2, 3]
^ ^ ^
The first triplet we enumerated using the triple loop is (0,1,2). If the third loop continues to enumerate the next element, it is still a triplet (0,1,2), resulting in duplication. Therefore, we need to "jump" the third loop to the next different element, that is, the last element 3 in the array, and enumerate the triples (0,1,3).
The pseudo code implementation of the improved method is given below:
nums.sort()
for first = 0 .. n-1
// We will enumerate only if the elements are different from those of the last enumeration
if first == 0 or nums[first] != nums[first-1] then
for second = first+1 .. n-1
if second == first+1 or nums[second] != nums[second-1] then
for third = second+1 .. n-1
if third == second+1 or nums[third] != nums[third-1] then
// Judge whether there is a+b+c==0
check(first, second, third)
The time complexity of this method is still O(N3). After all, we still haven't jumped out of the big framework of triple loop. However, it is easy to continue the optimization. It can be found that if we fix the elements a and B enumerated by the first two loops, then only the unique c satisfies a+b+c=0. When the second loop enumerates an element B ', since B' > b, c 'satisfying a+b' + c '= 0 must have c' < c, that is, c 'must appear on the left side of c in the array. In other words, we can enumerate B from small to large and c from large to small, that is, the second loop and the third loop are actually parallel.
With this discovery, we can keep the second loop unchanged and turn the third loop into a pointer moving to the left from the right end of the array, so as to obtain the following pseudo code:
nums.sort()
for first = 0 .. n-1
if first == 0 or nums[first] != nums[first-1] then
// Pointer corresponding to the third cycle
third = n-1
for second = first+1 .. n-1
if second == first+1 or nums[second] != nums[second-1] then
// Move the pointer to the left until a+b+c is not greater than 0
while nums[first]+nums[second]+nums[third] > 0
third = third-1
// Judge whether there is a+b+c==0
check(first, second, third)
This method is often called "double pointer". When we need to enumerate two elements in the array, if we find that the second element decreases with the increase of the first element, we can use the double pointer method to reduce the time complexity of enumeration from O(N2) to O(N). Why O(N)? This is because in each step of the enumeration process, the "left pointer" will move one position to the right (that is, b in the title), and the "right pointer" will move several positions to the left. This is related to the elements of the array, but we know that the total number of positions it will move is O(N), which is evenly spread, and it will also move one position to the left each time. Therefore, the time complexity is O(N).
Note that there is also the first loop in our pseudo code, and the time complexity is O(N), so the total time complexity of enumeration is O(N2). Since the time complexity of sorting is O(NlogN), which is less than the former in the progressive sense, the total time complexity of the algorithm is O(N2).