{"id":9375,"date":"2021-12-31T18:10:44","date_gmt":"2022-01-01T02:10:44","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9375"},"modified":"2021-12-31T18:26:20","modified_gmt":"2022-01-01T02:26:20","slug":"leetcode-1995-count-special-quadruplets","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-1995-count-special-quadruplets\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1995. Count Special Quadruplets"},"content":{"rendered":"\n<p>Given a&nbsp;<strong>0-indexed<\/strong>&nbsp;integer array&nbsp;<code>nums<\/code>, return&nbsp;<em>the number of&nbsp;<strong>distinct<\/strong>&nbsp;quadruplets<\/em>&nbsp;<code>(a, b, c, d)<\/code>&nbsp;<em>such that:<\/em><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>nums[a] + nums[b] + nums[c] == nums[d]<\/code>, and<\/li><li><code>a &lt; b &lt; c &lt; d<\/code><\/li><\/ul>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> nums = [1,2,3,6]\n<strong>Output:<\/strong> 1\n<strong>Explanation:<\/strong> The only quadruplet that satisfies the requirement is (0, 1, 2, 3) because 1 + 2 + 3 == 6.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> nums = [3,3,6,4,5]\n<strong>Output:<\/strong> 0\n<strong>Explanation:<\/strong> There are no such quadruplets in [3,3,6,4,5].\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> nums = [1,1,1,3,5]\n<strong>Output:<\/strong> 4\n<strong>Explanation:<\/strong> The 4 quadruplets that satisfy the requirement are:\n- (0, 1, 2, 3): 1 + 1 + 1 == 3\n- (0, 1, 3, 4): 1 + 1 + 3 == 5\n- (0, 2, 3, 4): 1 + 1 + 3 == 5\n- (1, 2, 3, 4): 1 + 1 + 3 == 5\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>4 &lt;= nums.length &lt;= 50<\/code><\/li><li><code>1 &lt;= nums[i] &lt;= 100<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 1: Brute force (224ms<\/strong>)<\/h2>\n\n\n\n<p>Enumerate a, b, c, d.<\/p>\n\n\n\n<p>Time complexity: O(C(n, 4)) = O(n<sup>4<\/sup>\/24)<br>Space complexity: O(1)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int countQuadruplets(vector<int>& nums) {\n    const int n = nums.size();\n    int ans = 0;\n    for (int a = 0; a < n; ++a)\n      for (int b = a + 1; b < n; ++b)\n        for (int c = b + 1; c < n; ++c)\n          for (int d = c + 1; d < n; ++d)\n            ans += nums[a] + nums[b] + nums[c] == nums[d];\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 2: Static <meta charset=\"utf-8\"><strong>frequency table<\/strong> + binary search (39ms)<\/strong><\/h2>\n\n\n\n<p>For each element, we store its indices (sorted).<\/p>\n\n\n\n<p>Given a, b, c, target t = nums[a] + nums[b] + nums[c], we check the hashtable and use binary search to find how many times it occurred after index c.<\/p>\n\n\n\n<p>Time complexity: O(n<sup>3<\/sup>\/6*logn)<br>Space complexity: O(n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int countQuadruplets(vector<int>& nums) {\n    constexpr int kMax = 100;\n    const int n = nums.size();\n    int ans = 0;\n    vector<vector<int>> m(kMax + 1);\n    for (int i = 0; i < n; ++i)\n      m[nums[i]].push_back(i);\n    for (int a = 0; a < n; ++a)\n      for (int b = a + 1; b < n; ++b)\n        for (int c = b + 1; c < n; ++c) {\n          const int t = nums[a] + nums[b] + nums[c];\n          if (t > kMax) continue;\n          ans += end(m[t]) - lower_bound(begin(m[t]), end(m[t]), c + 1);\n        }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<p><\/p>\n\n\n\n<p><\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 3: Dynamic frequency table (29ms)<\/strong><\/h2>\n\n\n\n<p>Similar to <a rel=\"noreferrer noopener\" href=\"https:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-1-two-sum\/\" data-type=\"post\" data-id=\"903\" target=\"_blank\">\u82b1\u82b1\u9171 LeetCode 1. Two Sum<\/a>, we dynamically add elements (from right to left) into the hashtable.<\/p>\n\n\n\n<p>Time complexity: O(n<sup>3<\/sup>\/6)<br>Space complexity: O(n)<\/p>\n\n\n\n<p><\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int countQuadruplets(vector<int>& nums) {\n    constexpr int kMax = 100;\n    const int n = nums.size();\n    int ans = 0;\n    vector<int> m(kMax + 1);    \n    \/\/ for every c we had seen, we can use it as target (nums[d]).\n    for (int c = n - 1; c >= 0; ++m[nums[c--]])\n      for (int a = 0; a < c; ++a)\n        for (int b = a + 1; b < c; ++b) {\n          const int t = nums[a] + nums[b] + nums[c];\n          if (t > kMax) continue;\n          ans += m[t];\n        }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given a&nbsp;0-indexed&nbsp;integer array&nbsp;nums, return&nbsp;the number of&nbsp;distinct&nbsp;quadruplets&nbsp;(a, b, c, d)&nbsp;such that: nums[a] + nums[b] + nums[c] == nums[d], and a &lt; b &lt; c &lt; d&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[149,70],"tags":[20,52,222,82],"class_list":["post-9375","post","type-post","status-publish","format-standard","hentry","category-binary-search","category-hashtable","tag-array","tag-binary-search","tag-easy","tag-hashtable","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9375","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=9375"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9375\/revisions"}],"predecessor-version":[{"id":9382,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9375\/revisions\/9382"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9375"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9375"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9375"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}