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 <stdlib.h>
2
3typedef struct {
4 int key;
5 int value;
6 UT_hash_handle hh;
7} HashMapItem;
8
9int fourSumCount(int* nums1, int nums1Size, int* nums2, int nums2Size, int* nums3, int nums3Size, int* nums4, int nums4Size) {
10 HashMapItem* hashMap = NULL;
11 HashMapItem* item;
12 int count = 0;
13
14 // Calculating sums of pairs from nums1 and nums2
15 for (int i = 0; i < nums1Size; i++) {
16 for (int j = 0; j < nums2Size; j++) {
17 int sum = nums1[i] + nums2[j];
18 HASH_FIND_INT(hashMap, &sum, item);
19 if (item == NULL) {
20 item = (HashMapItem*)malloc(sizeof(HashMapItem));
21 item->key = sum;
22 item->value = 1;
23 HASH_ADD_INT(hashMap, key, item);
24 } else {
25 item->value++;
26 }
27 }
28 }
29
30 // Calculating sums of pairs from nums3 and nums4
31 for (int k = 0; k < nums3Size; k++) {
32 for (int l = 0; l < nums4Size; l++) {
33 int sum = -(nums3[k] + nums4[l]);
34 HASH_FIND_INT(hashMap, &sum, item);
35 if (item != NULL) count += item->value;
36 }
37 }
38
39 // Free the hash map
40 HASH_CLEAR(hh, hashMap);
41
42 return count;
43}
44The given C solution defines a hash map structure using the UT hash library. It stores sums of pairs from nums1 and nums2 in a hash map. For each pair in nums3 and nums4, it checks how many complementary sums exist in the hash map, contributing to the tuple count.