Four Sum Count
Given four integer arrays A, B, C, and D, return the number of tuples (i,j,k,l) such that A[i] + B[j] + C[k] + D[l] = 0.
The efficient hash map strategy is to store all sums of pairs from A and B, then for each pair from C and D, add how many times the opposite sum appears.
This reduces complexity from O(n^4) to O(n^2).
Algorithm Flow

Recommendation Algorithm Flow for Four Sum Count - Budibadu
Best Answers
java
import java.util.*;
class Solution {
public int four_sum_count(int[] A, int[] B, int[] C, int[] D) {
Map<Integer, Integer> ab = new HashMap<>();
for (int a : A) {
for (int b : B) {
int s = a + b;
ab.put(s, ab.getOrDefault(s, 0) + 1);
}
}
int ans = 0;
for (int c : C) {
for (int d : D) {
ans += ab.getOrDefault(-(c + d), 0);
}
}
return ans;
}
}Comments (0)
Join the Discussion
Share your thoughts, ask questions, or help others with this problem.
