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
©2019-2020 Toolsou All rights reserved,
Error summary -myBatis plus paging use easyPOI Import Excel data In the problem of target detection “ recall Recall”,“ Accuracy Precision”vue use vue-clipboard2 Realize the function of copy link C In language switch sentence Wechat applet (uni-app)url Parameter transfer object hive compress &&hdfs Merge small files hive Summary of processing methods for a large number of small files use spring Of AntPathMatcher matching url route Linux Page replacement algorithm C Language implementation