{"id":8471,"date":"2021-08-04T22:48:38","date_gmt":"2021-08-05T05:48:38","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8471"},"modified":"2021-08-04T22:57:51","modified_gmt":"2021-08-05T05:57:51","slug":"leetcode-1865-finding-pairs-with-a-certain-sum","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-1865-finding-pairs-with-a-certain-sum\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1865. Finding Pairs With a Certain Sum"},"content":{"rendered":"\n

You are given two integer arrays nums1<\/code> and nums2<\/code>. You are tasked to implement a data structure that supports queries of two types:<\/p>\n\n\n\n

  1. Add<\/strong> a positive integer to an element of a given index in the array nums2<\/code>.<\/li>
  2. Count<\/strong> the number of pairs (i, j)<\/code> such that nums1[i] + nums2[j]<\/code> equals a given value (0 <= i < nums1.length<\/code> and 0 <= j < nums2.length<\/code>).<\/li><\/ol>\n\n\n\n

    Implement the FindSumPairs<\/code> class:<\/p>\n\n\n\n

    • FindSumPairs(int[] nums1, int[] nums2)<\/code> Initializes the FindSumPairs<\/code> object with two integer arrays nums1<\/code> and nums2<\/code>.<\/li>
    • void add(int index, int val)<\/code> Adds val<\/code> to nums2[index]<\/code>, i.e., apply nums2[index] += val<\/code>.<\/li>
    • int count(int tot)<\/code> Returns the number of pairs (i, j)<\/code> such that nums1[i] + nums2[j] == tot<\/code>.<\/li><\/ul>\n\n\n\n

      Example 1:<\/strong><\/p>\n\n\n\n

      Input<\/strong>\n[\"FindSumPairs\", \"count\", \"add\", \"count\", \"count\", \"add\", \"add\", \"count\"]\n[[[1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]], [7], [3, 2], [8], [4], [0, 1], [1, 1], [7]]\nOutput<\/strong>\n[null, 8, null, 2, 1, null, null, 11]\nExplanation<\/strong>\nFindSumPairs findSumPairs = new FindSumPairs([1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]);\nfindSumPairs.count(7); \/\/ return 8; pairs (2,2), (3,2), (4,2), (2,4), (3,4), (4,4) make 2 + 5 and pairs (5,1), (5,5) make 3 + 4\nfindSumPairs.add(3, 2); \/\/ now nums2 = [1,4,5,4<\/strong>,5,4] \nfindSumPairs.count(8); \/\/ return 2; pairs (5,2), (5,4) make 3 + 5 \nfindSumPairs.count(4); \/\/ return 1; pair (5,0) makes 3 + 1 \nfindSumPairs.add(0, 1); \/\/ now nums2 = [2<\/strong>,4,5,4,5,4] \nfindSumPairs.add(1, 1); \/\/ now nums2 = [2,5<\/strong>,5,4,5,4] \nfindSumPairs.count(7); \/\/ return 11; pairs (2,1), (2,2), (2,4), (3,1), (3,2), (3,4), (4,1), (4,2), (4,4) make 2 + 5 and pairs (5,3), (5,5) make 3 + 4\n<\/pre>\n\n\n\n
      Constraints:<\/strong><\/p>\n\n\n\n
      • 1 <= nums1.length <= 1000<\/code><\/li>
      • 1 <= nums2.length <= 105<\/sup><\/code><\/li>
      • 1 <= nums1[i] <= 109<\/sup><\/code><\/li>
      • 1 <= nums2[i] <= 105<\/sup><\/code><\/li>
      • 0 <= index < nums2.length<\/code><\/li>
      • 1 <= val <= 105<\/sup><\/code><\/li>
      • 1 <= tot <= 109<\/sup><\/code><\/li>
      • At most 1000<\/code> calls are made to add<\/code> and count<\/code> each<\/strong>.<\/li><\/ul>\n\n\n\n
        Solution: HashTable<\/strong><\/h2>\n\n\n\n
        Note nums1 and nums2 are unbalanced. Brute force method will take O(m*n) = O(103<\/sup>*105<\/sup>) = O(108<\/sup>) for each count call which will TLE. We could use a hashtable to store the counts of elements from nums2, and only iterate over nums1 to reduce the time complexity.<\/p>\n\n\n\n
        Time complexity:<\/p>\n\n\n\n
        init: O(m) + O(n)
        add: O(1)
        count: O(m)<\/p>\n\n\n\n
        Total time is less than O(106<\/sup>)<\/p>\n\n\n\n
        Space complexity: O(m + n)<\/p>\n\n\n\n
        \n
        C++<\/h2>\n
        \n\n
        \n\/\/ Author: Huahua\nclass FindSumPairs {\npublic:\n  FindSumPairs(vector& nums1, \n               vector& nums2): nums1_(nums1), nums2_(nums2) {\n    for (int x : nums2_) ++freq_[x];\n  }\n\n  void add(int index, int val) {\n    if (--freq_[nums2_[index]] == 0)\n      freq_.erase(nums2_[index]);\n    ++freq_[nums2_[index] += val];\n  }\n\n  int count(int tot) {\n    int ans = 0;\n    for (int a : nums1_) {\n      auto it = freq_.find(tot - a);\n      if (it != freq_.end()) ans += it->second;\n    }\n    return ans;\n  }\nprivate:  \n  vector nums1_;\n  vector nums2_;\n  unordered_map freq_;\n};\n<\/pre>\n\n<\/div>
        Python3<\/h2>\n
        \n\n
        \n# Author: Huahua\nclass FindSumPairs:\n  def __init__(self, nums1: List[int], nums2: List[int]):\n    self.nums1 = nums1\n    self.nums2 = nums2\n    self.freq = Counter(nums2)\n\n\n  def add(self, index: int, val: int) -> None:\n    self.freq.subtract((self.nums2[index],))\n    self.nums2[index] += val\n    self.freq.update((self.nums2[index],))\n\n\n  def count(self, tot: int) -> int:\n    return sum(self.freq[tot - a] for a in self.nums1)\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
        You are given two integer arrays nums1 and nums2. You are tasked to implement a data structure that supports queries of two types: Add a positive integer to an…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[70],"tags":[20,291,251,82],"class_list":["post-8471","post","type-post","status-publish","format-standard","hentry","category-hashtable","tag-array","tag-data-structure","tag-design","tag-hashtable","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8471","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=8471"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8471\/revisions"}],"predecessor-version":[{"id":8477,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8471\/revisions\/8477"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8471"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8471"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8471"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}