Four Sum Count

Like0

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).

Example 1:

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

Example 2:

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

Example 3:

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

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;
    }
}

javascript

function four_sum_count(A, B, C, D) {
    const ab = {};
    for (let i = 0; i < A.length; i++) {
        for (let j = 0; j < B.length; j++) {
            const s = A[i] + B[j];
            ab[s] = (ab[s] || 0) + 1;
        }
    }
    let ans = 0;
    for (let i = 0; i < C.length; i++) {
        for (let j = 0; j < D.length; j++) {
            ans += (ab[-(C[i] + D[j])] || 0);
        }
    }
    return ans;
}

php

<?php
function four_sum_count($A, $B, $C, $D) {
    $ab = [];
    foreach ($A as $a) {
        foreach ($B as $b) {
            $k = (string)($a + $b);
            $ab[$k] = ($ab[$k] ?? 0) + 1;
        }
    }
    $ans = 0;
    foreach ($C as $c) {
        foreach ($D as $d) {
            $need = (string)(-($c + $d));
            $ans += ($ab[$need] ?? 0);
        }
    }
    return $ans;
}
?>

python

from typing import List

def four_sum_count(A: List[int], B: List[int], C: List[int], D: List[int]) -> int:
    ab = {}
    for a in A:
        for b in B:
            s = a + b
            ab[s] = ab.get(s, 0) + 1
    ans = 0
    for c in C:
        for d in D:
            ans += ab.get(-(c + d), 0)
    return ans

rust

use std::collections::HashMap;
fn four_sum_count(A: Vec<i32>, B: Vec<i32>, C: Vec<i32>, D: Vec<i32>) -> i32 {
    let mut ab: HashMap<i32, i32> = HashMap::new();
    for a in A.iter() {
        for b in B.iter() {
            *ab.entry(*a + *b).or_insert(0) += 1;
        }
    }
    let mut ans = 0;
    for c in C.iter() {
        for d in D.iter() {
            ans += *ab.get(&(-(*c + *d))).unwrap_or(&0);
        }
    }
    ans
}

typescript

function four_sum_count(A: number[], B: number[], C: number[], D: number[]): number {
    var ab: { [key: string]: number } = {};
    for (var i = 0; i < A.length; i++) {
        for (var j = 0; j < B.length; j++) {
            var s = String(A[i] + B[j]);
            ab[s] = (ab[s] || 0) + 1;
        }
    }
    var ans = 0;
    for (var x = 0; x < C.length; x++) {
        for (var y = 0; y < D.length; y++) {
            var need = String(-(C[x] + D[y]));
            ans += (ab[need] || 0);
        }
    }
    return ans;
}

Comments (0)

Join the Discussion

Share your thoughts, ask questions, or help others with this problem.

Four Sum Count

Algorithm Flow

Best Answers

Solutions Coming Soon

Related Hash Table Problems

Duplicate Indices Map

First Unique Character

Contains Duplicate

Valid Anagram

Ransom Note

Two Sum Indices

Comments (0)

Join the Discussion