Finding pairs with a certain sum

Array Hash Table Design

61.6% acceptance

Feb 23, 2026

1036

145

You are given two integer arrays nums1 and nums2. Implement a data structure that supports queries of two types: Add a positive integer to an element of a given index in the array nums2. Count the number of pairs (i, j) such that nums1[i] + nums2[j] equals a given value. Implement the FindSumPairs class: FindSumPairs(int[] nums1, int[] nums2) Initializes the object. void add(int index, int val) Adds val to nums2[index]. int count(int tot) Returns the number of pairs (i, j) such that nums1[i] + nums2[j] == tot.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

use std::collections::HashMap;

pub struct FindSumPairs {
  nums1: Vec<i32>,
  nums2: Vec<i32>,
  freq2: HashMap<i32, i32>,
}

impl FindSumPairs {
  pub fn new(nums1: Vec<i32>, nums2: Vec<i32>) -> Self {
    let mut freq2 = HashMap::new();
    for &x in &nums2 {
      *freq2.entry(x).or_insert(0) += 1;
    }
    FindSumPairs { nums1, nums2, freq2 }
  }

  pub fn add(&mut self, index: i32, val: i32) {
    let idx = index as usize;
    let old = self.nums2[idx];
    *self.freq2.entry(old).or_insert(0) -= 1;
    if self.freq2[&old] == 0 {
      self.freq2.remove(&old);
    }
    self.nums2[idx] += val;
    *self.freq2.entry(self.nums2[idx]).or_insert(0) += 1;
  }

  pub fn count(&self, tot: i32) -> i32 {
    self.nums1.iter().map(|&a| {
      let need = tot - a;
      *self.freq2.get(&need).unwrap_or(&0)
    }).sum()
  }
}