{"id":1986,"date":"2018-03-05T21:28:31","date_gmt":"2018-03-06T05:28:31","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=1986"},"modified":"2018-03-06T08:48:52","modified_gmt":"2018-03-06T16:48:52","slug":"leetcode-454-4sum-ii","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-454-4sum-ii\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 454. 4Sum II"},"content":{"rendered":"
\n

\u9898\u76ee\u5927\u610f\uff1a\u7ed9\u4f604\u4e2a\u7ec4\u6570\uff1aA, B, C, D\u3002\u95ee\u6709\u591a\u5c11\u7ec4\u7ec4\u5408\u7684A[i] + B[j] + C[k] + D[l] \u7684\u548c\u4e3a0\u3002<\/p>\n

Given four lists A, B, C, D of integer values, compute how many tuples\u00a0(i, j, k, l)<\/code>\u00a0there are such that\u00a0A[i] + B[j] + C[k] + D[l]<\/code>is zero.<\/p>\n

To make problem a bit easier, all A, B, C, D have same length of N where 0 \u2264 N \u2264 500. All integers are in the range of -228<\/sup>\u00a0to 228<\/sup>\u00a0– 1 and the result is guaranteed to be at most 231<\/sup>\u00a0– 1.<\/p>\n

Example:<\/b><\/p>\n

Input:\r\nA = [ 1, 2]\r\nB = [-2,-1]\r\nC = [-1, 2]\r\nD = [ 0, 2]\r\n\r\nOutput:\r\n2\r\n\r\nExplanation:\r\nThe two tuples are:\r\n1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0\r\n2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0\r\n<\/pre>\n<\/div>\n
Solution 1: HashTable<\/strong><\/p>\n
Split the arrays into two groups: (A, B), (C, D)<\/p>\n
Create the Minkowski sum of two groups and count the occurrence of each element.<\/p>\n
e.g. A = [1, 2, 3], B = [0, -1, 1]<\/p>\n
Minkowski sum(A, B) SAB= [0, 1, 2, 3, 4] => [0:1, 1:2, 2:3, 3:2, 4:1]<\/p>\n
for each element s in SAB, check whether -s is in Minkowski sum(C, D) SCD<\/p>\n
ans = sum(SAB[s] * SCD[-s]), for all s, that s in SAB and -s in SCD<\/p>\n
Time complexity: O(n^2)<\/p>\n
Space complexity: O(n^2)<\/p>\n
C++<\/p>\n
\/\/ Author: Huahua\r\n\/\/ Running time: 217 ms\r\nclass Solution {\r\npublic:\r\n  int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {\r\n    unordered_map<int, int> sums;\r\n    for (int a : A)\r\n      for (int b : B)\r\n        ++sums[a + b];\r\n    int ans = 0;\r\n    for (int c : C)\r\n      for (int d : D) {\r\n        auto it = sums.find(- c - d);\r\n        if (it != sums.end()) ans += it->second;          \r\n      }\r\n    return ans;\r\n  }\r\n};<\/pre>\n
Python3<\/p>\n
\"\"\"\r\nAuthor: Huahua\r\nRunning time: 672 ms\r\n\"\"\"\r\nclass Solution:\r\n  def fourSumCount(self, A, B, C, D):\r\n    s = collections.Counter([a + b for a in A for b in B])\r\n    return sum(s[-c - d] for c in C for d in D)<\/pre>\n
 <\/p>\n
Related Problems:<\/strong><\/p>\n