第三章哈希表part02

454.四数相加 II

题目地址： https://leetcode.cn/problems/4sum-ii/

基于结点(键值对) 的记录

multimap 基于红黑树

时间复杂度 O(log(n))

Code :

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
                // 基础 思路  遍历 

                //但 复杂度 有点 大
                multimap<int , int> HashTable_Map_A_Add_B;
                multimap<int , int> HashTable_Map_C_Add_D;

                // unordered_map  规定 / 设定  不含 重复 的 键值对

                //multimap  设定 可以  含有  重复 的 键值对

                int temp_SUM_Two_Varable = 0;

                int i = 0 ;

                int j = 0 ;

                int len = end(nums1) - begin(nums1) ;

                int Count_SUM_Equal_0 = 0;

                int k = 0 ;

                i = 0 ;
                for( ; i < len ; i++ )
                {
                    j = 0 ;
                    for(  ; j < len ; j++ )
                    {
                        //HashTable_Map_A_Add_B[nums1[i] + nums2[j]] ++ ; 

                        HashTable_Map_A_Add_B.insert({nums1[i] + nums2[j],1});

                        //HashTable_Map_A_Add_B.insert(make_pair<int,int>(nums1[i] + nums2[j],1));

                    }

                    


                }


                i = 0 ;
                for( ; i < len ; i++ )
                {
                    j = 0 ;
                    for(  ; j < len ; j++ )
                    {
                        //HashTable_Map_C_Add_D[nums3[i] + nums4[j]] ++ ; 

                        HashTable_Map_C_Add_D.insert({nums3[i] + nums4[j],1});
                        //HashTable_Map_C_Add_D.insert(make_pair<int,int>(nums3[i] + nums4[j],1));

                    }


                }


                //定义 使用 非 前后 分离 逻辑 支持

              
                /////////////////////////

                //multimap<int , int>:: iterator it1;
                
                for(auto it1 = HashTable_Map_A_Add_B.begin() , end = HashTable_Map_A_Add_B.end() ;it1 != end  ; it1 = HashTable_Map_A_Add_B.upper_bound(it1->first) )
                {
                    //Count_SUM_Equal_0 += HashTable_Map_A_Add_B->second * (HashTable_Map_C_Add_D[HashTable_Map_A_Add_B->first].count) ;                 
                    //cout<<"it1->first = "<<it1->first<<endl;

                    //cout<<"it1->first * -1 = "<<it1->first * -1<<endl;

                    //cout<<"HashTable_Map_C_Add_D.count( "<<it1->first<<" * -1) = "<<HashTable_Map_C_Add_D.count( it1->first * -1)<<endl;

                    //cout<<"HashTable_Map_A_Add_B.count( "<<it1->first<<" * -1) = "<<HashTable_Map_A_Add_B.count( it1->first )<<endl;
                    // 注意  乘  的  内容
                    
                    Count_SUM_Equal_0 += HashTable_Map_A_Add_B.count( it1->first ) * HashTable_Map_C_Add_D.count( it1->first * -1) ;

                }
             
                



                return Count_SUM_Equal_0 ;




                


    }
};

基于下标的记录

unordered_map 基于哈希表

时间复杂度 O(1)

Code :

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
                // 基础 思路  遍历 

                //但 复杂度 有点 大
                unordered_map<int , int> HashTable_Map_A_Add_B;
                unordered_map<int , int> HashTable_Map_C_Add_D;

                // unordered_map  规定 / 设定  不含 重复 的 键值对

                //multimap  设定 可以  含有  重复 的 键值对

                int temp_SUM_Two_Varable = 0;

                int i = 0 ;

                int j = 0 ;

                int len = end(nums1) - begin(nums1) ;

                int Count_SUM_Equal_0 = 0;

                int k = 0 ;

                i = 0 ;
                for( ; i < len ; i++ )
                {
                    j = 0 ;
                    for(  ; j < len ; j++ )
                    {
                        HashTable_Map_A_Add_B[nums1[i] + nums2[j]] ++ ; 

                        //HashTable_Map_A_Add_B.insert({nums1[i] + nums2[j],1});

                        //HashTable_Map_A_Add_B.insert(make_pair<int,int>(nums1[i] + nums2[j],1));

                    }

                    


                }


                i = 0 ;
                for( ; i < len ; i++ )
                {
                    j = 0 ;
                    for(  ; j < len ; j++ )
                    {
                        auto index_Correspond = HashTable_Map_A_Add_B.find(-(nums3[i] + nums4[j]) );
                        if( index_Correspond != HashTable_Map_A_Add_B.end()  )
                        {
                          Count_SUM_Equal_0 += HashTable_Map_A_Add_B[-(nums3[i] + nums4[j])];

                        }

                        //HashTable_Map_C_Add_D[nums3[i] + nums4[j]] ++ ; 

                        //HashTable_Map_C_Add_D.insert({nums3[i] + nums4[j],1});
                        //HashTable_Map_C_Add_D.insert(make_pair<int,int>(nums3[i] + nums4[j],1));

                    }


                }


                //定义 使用 非 前后 分离 逻辑 支持

              
                /////////////////////////

                //multimap<int , int>:: iterator it1;
                /*
                for(auto it1 = HashTable_Map_A_Add_B.begin() , end = HashTable_Map_A_Add_B.end() ;it1 != end  ; it1 = HashTable_Map_A_Add_B.upper_bound(it1->first) )
                {
                    //Count_SUM_Equal_0 += HashTable_Map_A_Add_B->second * (HashTable_Map_C_Add_D[HashTable_Map_A_Add_B->first].count) ;                 
                    //cout<<"it1->first = "<<it1->first<<endl;

                    //cout<<"it1->first * -1 = "<<it1->first * -1<<endl;

                    //cout<<"HashTable_Map_C_Add_D.count( "<<it1->first<<" * -1) = "<<HashTable_Map_C_Add_D.count( it1->first * -1)<<endl;

                    //cout<<"HashTable_Map_A_Add_B.count( "<<it1->first<<" * -1) = "<<HashTable_Map_A_Add_B.count( it1->first )<<endl;
                    // 注意 你 乘  的  内容
                    
                    Count_SUM_Equal_0 += HashTable_Map_A_Add_B.count( it1->first ) * HashTable_Map_C_Add_D.count( it1->first * -1) ;

                }
                
                */
                



                return Count_SUM_Equal_0 ;




                


    }
};

JZTXT

第三章 哈希表**part02**

第三章 哈希表**part02**

454.四数相加 II

第三章哈希表part02

第三章哈希表part02