526互联

代码随想录算法训练营第六天| 454.四数相加II 383. 赎金信 15. 三数之和 18. 四数之和

发布时间 2023-06-13 14:56:01作者: 博二爷

454.四数相加II

1，难点：

　　1，多个数组之间，会有重复出现的数组，如果单用multiset也是会出错的

　　2，如果用mutliset，在使用 distance 找出来 equal_range的值的时候，也是会出现奇怪的错误的

2，正确思路

　　1，把重复出现的节点，次数 存放到map种，然后进行遍历

3，代码：

 1 int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4)
 2 {
 3     int result = 0;
 4     unordered_map<int,int> selected;
 5     for (int num1 : nums1)
 6     {
 7         for (int num2 : nums2)
 8         {
 9             if (selected.find(num1 + num2) == selected.end())
10             {
11                 selected.insert(make_pair(num1 + num2, 0));
12             }
13             selected[num1 + num2] ++;
14         }
15     }
16 
17     for (int num3 : nums3)
18     {
19         for (int num4 : nums4)
20         {
21             //或许可以判断target里面有几个pair
22             auto target = selected.find(-(num3 + num4));
23             if (target != selected.end())
24             {
25                 result += target->second;
26             }
27         }
28     }
29 
30     return result;
31 }