题目大意：给你4个组数：A, B, C, D。问有多少组组合的A[i] + B[j] + C[k] + D[l] 的和为0。
Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l]is zero.
To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -228 to 228 – 1 and the result is guaranteed to be at most 231 – 1.
Example:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
Input: A = [ 1, 2] B = [-2,-1] C = [-1, 2] D = [ 0, 2] Output: 2 Explanation: The two tuples are: 1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0 2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0 |
Solution 1: HashTable
Split the arrays into two groups: (A, B), (C, D)
Create the Minkowski sum of two groups and count the occurrence of each element.
e.g. A = [1, 2, 3], B = [0, -1, 1]
Minkowski sum(A, B) SAB= [0, 1, 2, 3, 4] => [0:1, 1:2, 2:3, 3:2, 4:1]
for each element s in SAB, check whether -s is in Minkowski sum(C, D) SCD
ans = sum(SAB[s] * SCD[-s]), for all s, that s in SAB and -s in SCD
Time complexity: O(n^2)
Space complexity: O(n^2)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// Author: Huahua // Running time: 217 ms class Solution { public: int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) { unordered_map<int, int> sums; for (int a : A) for (int b : B) ++sums[a + b]; int ans = 0; for (int c : C) for (int d : D) { auto it = sums.find(- c - d); if (it != sums.end()) ans += it->second; } return ans; } }; |
Python3
|
1 2 3 4 5 6 7 8 |
""" Author: Huahua Running time: 672 ms """ class Solution: def fourSumCount(self, A, B, C, D): s = collections.Counter([a + b for a in A for b in B]) return sum(s[-c - d] for c in C for d in D) |
Related Problems:
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
[…] 花花酱 LeetCode 454. 4Sum II […]