4Sum II – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Given four integer arrays nums1
, nums2
, nums3
, and nums4
all of length n
, return the number of tuples (i, j, k, l)
such that:
0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
Example 1:
Input: nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2] Output: 2 Explanation: The two tuples are: 1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0 2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0
Example 2:
Input: nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0] Output: 1
Constraints:
n == nums1.length
n == nums2.length
n == nums3.length
n == nums4.length
1 <= n <= 200
-228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228
C++ 4Sum II LeetCode Solution
int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
unordered_map<int, int> abSum;
for(auto a : A) {
for(auto b : B) {
++abSum[a+b];
}
}
int count = 0;
for(auto c : C) {
for(auto d : D) {
auto it = abSum.find(0 - c - d);
if(it != abSum.end()) {
count += it->second;
}
}
}
return count;
}
Java 4Sum II LeetCode Solution
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
var pairCountBySum = new HashMap<Integer, Integer>();
Arrays.stream(nums1)
.forEach(num1 -> Arrays.stream(nums2)
.forEach(num2 -> pairCountBySum.compute(num1 + num2, (k, sumCount) -> sumCount == null ? 1 : ++sumCount)));
return Arrays.stream(nums3)
.map(num3 -> Arrays.stream(nums4)
.map(num4 -> pairCountBySum.getOrDefault(-(num3 + num4), 0))
.sum())
.sum();
}
Python 3 4Sum II LeetCode Solution
def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
n, hm, res = len(nums1), defaultdict(int), 0
for i in range(n):
for j in range(n):
hm[nums1[i] + nums2[j]] += 1
for k in range(n):
for l in range(n):
res += hm[0 - (nums3[k] + nums4[l])]
return res
Array-1180
String-562
Hash Table-412
Dynamic Programming-390
Math-368
Sorting-264
Greedy-257
Depth-First Search-256
Database-215
Breadth-First Search-200
Tree-195
Binary Search-191
Matrix-176
Binary Tree-160
Two Pointers-151
Bit Manipulation-140
Stack-133
Heap (Priority Queue)-117
Design-116
Graph-108
Simulation-103
Prefix Sum-96
Backtracking-92
Counting-86
Sliding Window-73
Linked List-69
Union Find-66
Ordered Set-48
Monotonic Stack-47
Recursion-43
Trie-41
Binary Search Tree-40
Divide and Conquer-40
Enumeration-39
Bitmask-37
Queue-33
Memoization-32
Topological Sort-31
Geometry-30
Segment Tree-27
Game Theory-24
Hash Function-24
Binary Indexed Tree-21
Interactive-18
Data Stream-17
String Matching-17
Rolling Hash-17
Shortest Path-16
Number Theory-16
Combinatorics-15
Randomized-12
Monotonic Queue-9
Iterator-9
Merge Sort-9
Concurrency-9
Doubly-Linked List-8
Brainteaser-8
Probability and Statistics-7
Quickselect-7
Bucket Sort-6
Suffix Array-6
Minimum Spanning Tree-5
Counting Sort-5
Shell-4
Line Sweep-4
Reservoir Sampling-4
Eulerian Circuit-3
Radix Sort-3
Strongly Connected Componen-t2
Rejection Sampling-2
Biconnected Component-1