Skip to content

1865. Finding Pairs With a Certain Sum 👍

  • Time:
    • Constructor: $O(|\texttt{nums1}| + |\texttt{nums2}|)$
    • add(index: int, val: int): $O(1)$
    • count(tot: int): $O(|\texttt{nums1}|)$
  • Space: $O(|\texttt{nums2}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class FindSumPairs {
 public:
  FindSumPairs(vector<int>& nums1, vector<int>& nums2)
      : nums1(nums1), nums2(nums2) {
    for (const int num : nums2)
      ++count2[num];
  }

  void add(int index, int val) {
    --count2[nums2[index]];
    nums2[index] += val;
    ++count2[nums2[index]];
  }

  int count(int tot) {
    int ans = 0;
    for (const int num : nums1) {
      const int target = tot - num;
      if (const auto it = count2.find(target); it != count2.cend())
        ans += it->second;
    }
    return ans;
  }

 private:
  vector<int> nums1;
  vector<int> nums2;
  unordered_map<int, int> count2;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class FindSumPairs {
  public FindSumPairs(int[] nums1, int[] nums2) {
    this.nums1 = nums1;
    this.nums2 = nums2;
    for (final int num : nums2)
      count2.merge(num, 1, Integer::sum);
  }

  public void add(int index, int val) {
    count2.merge(nums2[index], -1, Integer::sum);
    nums2[index] += val;
    count2.merge(nums2[index], 1, Integer::sum);
  }

  public int count(int tot) {
    int ans = 0;
    for (final int num : nums1)
      ans += count2.getOrDefault(tot - num, 0);
    return ans;
  }

  private int[] nums1;
  private int[] nums2;
  private Map<Integer, Integer> count2 = new HashMap<>();
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class FindSumPairs:
  def __init__(self, nums1: list[int], nums2: list[int]):
    self.nums1 = nums1
    self.nums2 = nums2
    self.count2 = collections.Counter(nums2)

  def add(self, index: int, val: int) -> None:
    self.count2[self.nums2[index]] -= 1
    self.nums2[index] += val
    self.count2[self.nums2[index]] += 1

  def count(self, tot: int) -> int:
    ans = 0
    for num in self.nums1:
      ans += self.count2[tot - num]
    return ans