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;