3sum with multiplicity

Array Hash Table Two Pointers Sorting Counting

46.2% acceptance

Feb 25, 2026

2680

329

Given an integer array arr, and an integer target, return the number of tuples i, j, k such that i < j < k and arr[i] + arr[j] + arr[k] == target. As the answer can be very large, return it modulo 109 + 7.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn three_sum_multi(arr: Vec<i32>, target: i32) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let mut cnt = [0i64; 101];
    for &x in &arr { cnt[x as usize] += 1; }
    let mut ans: i64 = 0;
    for i in 0..=100i32 {
      for j in i..=100i32 {
        let k = target - i - j;
        if k < 0 || k > 100 { continue; }
        let (ci, cj, ck) = (cnt[i as usize], cnt[j as usize], cnt[k as usize]);
        if i == j && j == k {
          ans += ci * (ci - 1) * (ci - 2) / 6;
        } else if i == j && j != k {
          ans += ci * (ci - 1) / 2 * ck;
        } else if j < k {
          ans += ci * cj * ck;
        }
      }
    }
    (ans % MOD) as i32
  }
}