代码随想录算法练习营第七天-哈希-454. 四数相加II

• 力扣原题链接：454. 四数相加 II
  
• 使用map这个数据结构来保存前两个集合元素和的结果，value的值代表和这个值的出现的次数
  
• 使用这个方法，可以让算法复杂度从                                                   n                               4                                            n^4                     n4降落到                                                   n                               2                                            n^2                     n2，效率会大大提高
  

1. #include <iostream>
2. #include <vector>
3. #include <unordered_map>
5. class Solution {
6. public:
7.     int fourSumCount(std::vector<int>& nums1, std::vector<int>& nums2, std::vector<int>& nums3, std::vector<int>& nums4) {
8.         std::unordered_map<int, int> twoNumSums;
9.         for (auto n1: nums1)
10.             for (auto n2: nums2)
11.                 twoNumSums[n1 + n2]++;
12.         int count = 0;
13.         for (auto n3: nums3)
14.             for (auto n4: nums4) {
15.                 if (twoNumSums.find(0 - n3 - n4) != twoNumSums.end())
16.                     count += twoNumSums[0 - n3 - n4];
17.             }
18.         return count;
19.     }
20. };
21. int main()
22. {
23.     std::vector<int> num1 {1, 2};
24.     std::vector<int> num2 {-2, -1};
25.     std::vector<int> num3 {-1, 2};
26.     std::vector<int> num4 {0, 2};
27.     Solution s;
28.     std::cout << s.fourSumCount(num1, num2, num3, num4) << std::endl;
29.     return 0;
30. }

复制代码

• 汇总
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。