Sponsored
Sponsored
This approach leverages hash maps to efficiently count and use pair sums. First, we compute all possible sums between arrays nums1 and nums2, storing them in a hash map along with their count. Then, we iterate over pairs of nums3 and nums4, checking how many complements (to form a sum of zero) exist in the hash map.
Time Complexity: O(n^2), with each pair calculation taking constant time.
Space Complexity: O(n^2), using space for hash map storage.
1#include <unordered_map>
2#include <vector>
3using namespace std;
4
5int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
6 unordered_map<int, int> sumMap;
7 int count = 0;
8
9 for (int a : nums1) {
10 for (int b : nums2) {
11 sumMap[a + b]++;
12 }
13 }
14
15 for (int c : nums3) {
16 for (int d : nums4) {
17 int complement = -(c + d);
18 if (sumMap.count(complement)) {
19 count += sumMap[complement];
20 }
21 }
22 }
23
24 return count;
25}
26In this solution, we utilize C++’s unordered_map to store the sums of elements from nums1 and nums2. We then iterate over pairs from nums3 and nums4, checking for sums that zero out when added to existing ones in the map, leading to a count increment.