4sum ii

Array Hash Table

57.8% acceptance

Jan 13, 2026

5071

151

Given four integer arrays nums1, nums2, nums3, and nums4 all of length n, return the number of tuples (i, j, k, l) such that: 0 <= i, j, k, l < n nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

use std::collections::HashMap;

impl Solution {
  pub fn four_sum_count(nums1: Vec<i32>, nums2: Vec<i32>, nums3: Vec<i32>, nums4: Vec<i32>) -> i32 {
    let mut map = HashMap::new();
    
    for &a in &nums1 {
      for &b in &nums2 {
        *map.entry(a + b).or_insert(0) += 1;
      }
    }
    
    let mut count = 0;
    for &c in &nums3 {
      for &d in &nums4 {
        count += map.get(&(-(c + d))).unwrap_or(&0);
      }
    }
    
    count
  }
}