LeetCode #454 4Sum II
Problem
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 -2^28 to 2^28–1 and the result is guaranteed to be at most 2^31–1.
Example:
Input:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]Output:
2Explanation:
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
Use a hash map to save sum of all pairs of first two lists. And then iterate all pairs of other two lists to find its negative one.
Complexity
It’s trivial that it takes O(n²) time to count pairs of A and B. And it takes O(n²)/O(n² * log(n²)) time to check if negative of all pairs of C and D in hash map in average/worst cases. Finally, it takes O(n²) time to sum all counts. Therefore, its time complexity will be O(n² + n² + n²)/O(n² + n²logn + n²) = O(n²)/O(n²logn) in average/worst cases.
For space complexity, it uses O(n²) extra space for the hash map.
