4Sum II

Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.

Example:

Input:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]

Output:
2

Approach

Java

import java.util.HashMap;
import java.util.Map;

public class FourSumII {
    public static void main(String[] args) {
        int[] A = { 1, 2 };
        int[] B = { -2, -1 };
        int[] C = { -1, 2 };
        int[] D = { 0, 2 };
        System.out.println(fourSumCount(A, B, C, D));
    }

    static public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
        int zero = 0;
        Map<Integer, Integer> m = new HashMap<>();
        for (int i : A) {
            for (int j : B) {
                int s = i + j;
                m.put(s, m.getOrDefault(s, 0) + 1);

            }

        }

        for (int k : C)
            for (int l : D) {
                int s = k + l;
                zero += m.getOrDefault(-s, 0);
            }
        return zero;
    }

}

C++

#include <bits/stdc++.h>
using namespace std;

int fourSumCount(vector<int> &A, vector<int> &B, vector<int> &C, vector<int> &D)
{
    int n = A.size();
    if (n == 0)
        return 0;
    int sum = 0;
    unordered_map<int, int> mp1;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            int x = A[i] + B[j];
            mp1[x]++;
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (mp1.find(sum - (C[i] + D[j])) != mp1.end())
                ans += mp1[-(C[i] + D[j])];
        }
    }
    return ans;
}
int main()
{
    vector<int> A = {1, 2};
    vector<int> B = {-2, -1};
    vector<int> C = {-1, 2};
    vector<int> D = {0, 2};
    cout << fourSumCount(A, B, C, D);
    return 0;
}