四数相加
四个数字和为0 ， 统计前两个数的和出现次数。然后统计后两个数和是0减两个数和的情况。
class Solution { public: int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) { unordered_map<int, int> num_map; for (int i = 0; i < nums1.size(); i++) { for (int j = 0; j < nums2.size(); j++) { num_map[ nums1[i] + nums2[j] ]++; } } int count = 0; for (int i = 0; i < nums3.size(); i++) { for (int j = 0; j < nums4.size(); j++) { if (num_map.find(0 - nums3[i] - nums4[j]) != num_map.end()) count += num_map[0 - nums3[i] - nums4[j]]; } } return count; } };
cpp11写法
class Solution { public: int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) { unordered_map<int, int> num_map; for (auto i : nums1) { for (auto j : nums2) { num_map[ i+j ]++; } } int count = 0; for (auto i : nums3) { for (auto j : nums4 ) { if (num_map.find(0 - i- j) != num_map.end()) count += num_map[0 - i - j]; } } return count; } };
二刷
class Solution { public: int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) { int result = 0; unordered_map<int,int> my_map; for(int i=0 ; i<nums1.size() ;i++) { for(int j=0 ; j<nums2.size() ;j++) { my_map[nums1[i] + nums2[j]]++; } } for(int i=0 ; i<nums3.size() ;i++) { for(int j=0 ; j<nums4.size() ;j++) { if(my_map.find(0-nums3[i]-nums4[j]) != my_map.end()) result += my_map[0-nums3[i]-nums4[j]]; } } return result; } };
