Leetcode 15. sum of three numbers

Random code recording   Hashtable -8

15. Sum of three numbers

secondary  

Give you one containing  n  Array of integers  nums, Judge  nums  Are there three elements in  a,b,c , bring  a + b + c = 0 ？ Please find out all and for  0  Triple without repetition .

Be careful ： Answer cannot contain duplicate triples .

Example 1：

 Input ：nums = [-1,0,1,2,-1,-4]
 Output ：[[-1,-1,2],[-1,0,1]]

Example 2：

 Input ：nums = []
 Output ：[]

Example 3：

 Input ：nums = [0]
 Output ：[]

Method 1： Try it yourself

After a lot of hard work, I can barely run , But the time complexity is too high , Can pass 225/331 A sample , Niuke can pass 24/25 A sample （ Finally, because the space is too ）. It's numb , The general idea is similar to the sum of two numbers and four numbers , First go through it and find the sum of two numbers , Stored in hash table mp and mp_index in （ You have to save two hash tables , Two hash tables key Are the sum of two numbers ,value A stored value , Another save subscript ）, Finally, traverse again to find mp Yes no key For the opposite number of each element , If there is , Insert to the last result.( In the insert Result There are also many details , such as vector You can't vector.find, Can only find(vector.begin(),vector.end(),k),  Another example is extraction vector The penultimate element requires *(vector.end()-2) ,.end() Returns the terminating iterator ,-2 In the future, the iterator will be returned , Get it * To retrieve the element . wait ）

Unfortunately, it didn't pass completely in the end , To make the 2 One and a half hours , But it is also very progressive .

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        //  Try it yourself ,2022 year 7 month 20 Japan  16 spot 55 branch --17:43  Didn't do it ----19:00 Continue to do --20:49 d Probably passed , It's just that the time complexity is too high 
        //  Violent solution , First double for  Traversal fills the sum of two numbers , Find the third number 
        //  Hashtable key Is the sum of two numbers ,value  Save two values ( Multiple values , There may be more than two pairs )
        unordered_map<int, vector<int>> mp;
        unordered_map<int, vector<int>> mp_index;
        for(int i = 0; i < nums.size(); i++){
            for(int j = i + 1; j < nums.size(); j++){ 
                mp[nums[i] + nums[j]].push_back(nums[i]);
                mp[nums[i] + nums[j]].push_back(nums[j]);
                mp_index[nums[i] + nums[j]].push_back(i);
                mp_index[nums[i] + nums[j]].push_back(j);                
            }
        }

        vector<vector<int>> result;
        for(int k = 0; k < nums.size(); k++){
            auto it = mp.find(-nums[k]);
            if(it != mp.end()){
                //  We have to make sure  nums[k]  Do not repeat with the previous two numbers ---- incorrect , Are the first two subscripts 
                auto it_index = mp_index.find(-nums[k]);
                vector<int> sum_index = it_index->second;

                //  Be careful ：vector Out-of-service  vector.find, because find No vector Properties of 
                //  It is  vector  Function of , You can only  find(vector.begin(),vector.end(),3)
                // find(sum.begin(),sum.end(),nums[k]) == sum.end()

                // cout <<" And for ："<< it->first << ": {"; 
                // for(int nuu : it->second){
                //     cout << nuu <<" ";
                // }
                // cout <<"}" << " Subscript to be ：{";

                // for(int nnu : sum_index){
                //     cout << nnu <<" ";
                // }
                // cout <<"}" <<endl;
                    
                while(!it->second.empty()){
                    //nums[k]  And the last two numbers of the array [ The subscript ] No repetition , Insert     
                    if(find(sum_index.end()-2,sum_index.end(),k) == sum_index.end()){
                        vector<int> tmp;
                        tmp.push_back(nums[k]);
                        // Insert two from the back and delete the last two , Until it's gone 
                        tmp.push_back(it->second.back());
                        //  second to last , Must use end()-2, And then use * Value 
                        tmp.push_back(*(it->second.end()-2));
                        
                        result.push_back(tmp);
                    }
                    it->second.pop_back();
                    it->second.pop_back();
                    // sum_index  have no choice but to pop_back--- Error discovery of the second submission 
                    sum_index.pop_back();
                    sum_index.pop_back();
                }

                // // Delete duplicate elements in the result 
                // for(int m = 0; m < result.size(); m++){
                //     vector<int> tmp1 = result[m];
                //     sort(tmp1.begin(),tmp1.end());
                //     for(int n = m+1; n < result.size(); n++){
                //         vector<int> tmp2 = result[n];
                //         sort(tmp2.begin(),tmp2.end());
                //         if(tmp1 == tmp2){
                //             result.erase(result.begin() + n);
                //             n--;
                //         }
                //     }
                // }

                //  use set  Will it be faster to delete duplicate elements 
                for(int m = 0; m < result.size(); m++){
                    unordered_set<int> set1(result[m].begin(),result[m].end()); 
                    for(int n = m+1; n < result.size(); n++){
                        unordered_set<int> set2(result[n].begin(),result[n].end());
                        if(set1 == set2){
                            result.erase(result.begin() + n);
                            n--;
                        }
                    }
                }



                // for(vector<int> out_res : result){
                //     cout << "[";
                //     for(int in_res: out_res){
                //         cout<< in_res <<", ";
                //     }
                //     cout << "],";
                // }
                // cout <<endl;   
            }
        }

        // // Finally, delete the repeated elements in the result 
        // for(int m = 0; m < result.size(); m++){
        //     vector<int> tmp1 = result[m];
        //     sort(tmp1.begin(),tmp1.end());
        //     for(int n = m+1; n < result.size(); n++){
        //         vector<int> tmp2 = result[n];
        //         sort(tmp2.begin(),tmp2.end());
        //         if(tmp1 == tmp2){
        //             result.erase(result.begin() + n);
        //             // erase after result.size() Will be reduced 1, therefore n  Also have to reduce ,
        //             //  The test case 222 [3,0,3,2,-4,0,-3,2,2,0,-1,-5]  Find out 
        //             n--;
        //         }
        //     }
        // }

        // //  use set  Will it be faster to delete duplicate elements 
        // for(int m = 0; m < result.size(); m++){
        //     unordered_set<int> set1(result[m].begin(),result[m].end()); 
        //     for(int n = m+1; n < result.size(); n++){
        //         unordered_set<int> set2(result[n].begin(),result[n].end());
        //         if(set1 == set2){
        //             result.erase(result.begin() + n);
        //             n--;
        //         }
        //     }
        // }

        return result;
    }
};