Topic requirements ：
Given an inclusion n An array of integers nums, judge nums Are there three elements in a,b,c , bring a + b + c = 0
? Find all triples that satisfy the condition and do not repeat .
be careful ： The answer cannot contain duplicate triples .
Xiaobai's first blog , I hope you can give me more advice .
This is an array Title marked medium on the collar button , The difficulty of the problem is to remove the repeated triples . We want to get rid of repetitive elements , We need to find out , How do repeated answers come out , In the normal way , We can run a three story for loop , Each time, it's constantly matched by the front and the back , Until all combinations are matched , The answer that meets the requirements is found , But in the course of running, if the number in front of you is repeated with that in the back , Then we must record it twice in the course of running . Find out the reason for the repetition , Now we need to find a way to eliminate duplication . In this way, the problem becomes the de duplication of arrays , Array de duplication we generally use the method of sorting first , Front vs. back , duplicate removal .
According to our idea, the code is as follows ：
// programing language c++
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> a;// Create container
int len=nums.size();
vector<int>temp;// Intermediate variable , It is used to save the result of each time
if(nums.size()<=2)
return a;// If the length of the given array is less than 3, Direct return
sort(nums.begin(),nums.end());// use sort Method to sort the data
int i,j,k,sum;
for(i=0;i<len-2;i++)// First cycle
{
if(nums[i]>0)//nums[0] If greater than 0 Represents that the data are all positive numbers , immediate withdrawal
break;
if(i>0&&nums[i]==nums[i-1])// Used to remove duplicate values , Use only the first occurrence of data
continue;
j=i+1;
while(j<=len-2)
{
if(j>i+1&&nums[j]==nums[j-1])// duplicate removal
{
j++;
continue;
}
k=j+1;
while(k<=len-1)
{
if(k>j+1&&nums[k]==nums[k-1])// duplicate removal
{
k++;
continue;
}
sum=nums[i]+nums[j]+nums[k];
if(sum==0)
{
temp.push_back(nums[i]);
temp.push_back(nums[j]);
temp.push_back(nums[k]);
a.push_back(temp);
temp.clear();// empty
k++;
}
else
k++;
}
j++;
}
}
return a;
}
};
After submission , Timeout will be prompted , So we improved the code , Considering the triple existence for The loop is to get and 0 Matching results , After learning from the boss's method , We can change it to a double cycle , Make use of the principle of leaning forward and backward in the middle , Looking for answers . This is a basic skill in programming , If you don't master it, you can learn from it , The changed code is as follows ：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> a;
int len=nums.size();
vector<int>temp;
if(nums.size()<=2)
return a;
sort(nums.begin(),nums.end());
int i,j,k,sum;
for(i=0;i<len-2;i++)
{
if(nums[i]>0)
break;
if(i>0&&nums[i]==nums[i-1])
continue;
j=i+1;// Front end of unmatched data
k=len-1; Back end of unmatched data
while(j<k)// If there is a crossover , Then it means that all the subsequent data are matched
{
if(j>i+1&&nums[j]==nums[j-1])// Used to remove duplicate values , because k Every time I find it, I jump out , So there's no need to redo the operation
{
j++;
continue;
}
sum=nums[i]+nums[j]+nums[k];
if(sum==0)// Save data
{
temp.push_back(nums[i]);
temp.push_back(nums[j]);
temp.push_back(nums[k]);
a.push_back(temp);
temp.clear();
j++;
}
else if(sum>0)// If greater than 0 If the data is too large, it will k reduce , Is matched k Value decreases
k--;
else
j++;
}
}
return a;
}
};
You can find that this time it was easy to pass , After finishing the problem, we can try to do it 16,18 Two questions , The idea is roughly the same .
Technology
Daily Recommendation