·

# Problem statement

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

• `nums1.length = nums2.length = nums3.length = nums4.length = n`.
• `1 <= n <= 200`.
• `-2^28 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 2^28`.

# Solution 1: Four loops

## Code

``````#include <iostream>
#include <vector>
using namespace std;
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
int count = 0;
for (auto& n1 : nums1) {
for (auto& n2 : nums2) {
for (auto& n3 : nums3) {
for (auto& n4 : nums4) {
if (n1 + n2 + n3 + n4 == 0) {
count++;
}
}
}
}
}
return count;
}
int main() {
vector<int> nums1, nums2, nums3, nums4;
nums1 = {1, 2};
nums2 = {-2, -1};
nums3 = {-1, 2};
nums4 = {0, 2};
cout << fourSumCount(nums1, nums2, nums3, nums4) << endl;
nums1 = {0};
nums2 = {0};
nums3 = {0};
nums4 = {0};
cout << fourSumCount(nums1, nums2, nums3, nums4) << endl;
}
``````
``````Output:
2
1
``````

## Complexity

• Runtime: `O(n^4)`.
• Extra memory: `O(1)`.

# Solution 2: Two loops

Rewriting `nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0` as `nums1[i] + nums2[j] == 0 - nums3[k] - nums4[l]` you could reduce the runtime complexity of the solution above from `O(n^4)` to `O(n^2)` by storing the sum `nums1[i] + nums2[j]` in a map.

## Code

``````#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
int count = 0;
unordered_map<int, int> sumTwo;
for (auto& n1 : nums1) {
for (auto& n2 : nums2) {
sumTwo[n1 + n2]++;
}
}
for (auto& n3 : nums3) {
for (auto& n4 : nums4) {
auto it = sumTwo.find(0 - n3 - n4);
if (it != sumTwo.end()) {
count += it->second;
}
}
}
return count;
}
int main() {
vector<int> nums1, nums2, nums3, nums4;
nums1 = {1, 2};
nums2 = {-2, -1};
nums3 = {-1, 2};
nums4 = {0, 2};
cout << fourSumCount(nums1, nums2, nums3, nums4) << endl;
nums1 = {0};
nums2 = {0};
nums3 = {0};
nums4 = {0};
cout << fourSumCount(nums1, nums2, nums3, nums4) << endl;
}
``````
``````Output:
2
1
``````

## Complexity

• Runtime: `O(n^2)`.
• Extra memory: `O(n^2)`.