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.
1import java.util.HashMap;
2import java.util.Map;
3
4public class FourSumII {
5 public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
6 Map<Integer, Integer> map = new HashMap<>();
7 int count = 0;
8
9 for (int a : nums1) {
10 for (int b : nums2) {
11 map.put(a + b, map.getOrDefault(a + b, 0) + 1);
12 }
13 }
14
15 for (int c : nums3) {
16 for (int d : nums4) {
17 count += map.getOrDefault(-(c + d), 0);
18 }
19 }
20
21 return count;
22 }
23}
24Java's implementation uses a HashMap to store sums of the first two arrays. Then, for each pair sum from nums3 and nums4, it looks up the complement in the map, adding the number of observed pairs contributing to the zero sum.