Description
Given a 0-indexed integer array nums, return the number of distinct quadruplets (a, b, c, d) such that:
nums[a] + nums[b] + nums[c] == nums[d], anda < b < c < d
Solution
Recall how we solve TwoSum.
Since we have the constraint of a < b < c < d. We should iterate nums from back, insert numbers as nums[d] (also backwards) to the map on the fly and use three loops to iterate the numbers backwards. By checking if the sum exist in map, we could get the number of quadruplets.
Implementation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int countQuadruplets(vector<int>& nums) {
int count = 0, n = nums.size();
unordered_map<int, int> map;
map[nums.back()]++;
for (int i = n-2; i >= 2; i--) {
for (int j = i-1; j >= 1; j--) {
for (int k = j-1; k >= 0; k--) {
int sum = nums[i] + nums[j] + nums[k];
if (map.find(sum) != map.end()) count += map[sum];
}
}
map[nums[i]]++;
}
return count;
}
};