Sponsored
Sponsored
This approach involves first sorting the array and then using a two-pointer method to efficiently count the valid tuples. After fixing the first element of the triplet, use two pointers to find complementary pairs that sum up to the required value.
Time Complexity: O(n^2), where n is the number of elements in the array.
Space Complexity: O(1) apart from the input data since the operation is done in-place.
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6class Solution {
7public:
8 int threeSumMulti(vector<int>& arr, int target) {
9 sort(arr.begin(), arr.end());
10 const int MOD = 1e9 + 7;
11 long result = 0;
12 int n = arr.size();
13 for (int i = 0; i < n; ++i) {
14 int T = target - arr[i];
15 int j = i + 1, k = n - 1;
16 while (j < k) {
17 if (arr[j] + arr[k] < T) {
18 ++j;
19 } else if (arr[j] + arr[k] > T) {
20 --k;
21 } else {
22 if (arr[j] != arr[k]) {
23 int left = 1, right = 1;
24 while (j + 1 < k && arr[j] == arr[j + 1]) {
25 ++left;
26 ++j;
27 }
28 while (k - 1 > j && arr[k] == arr[k - 1]) {
29 ++right;
30 --k;
31 }
32 result += left * right;
33 result %= MOD;
34 ++j;
35 --k;
36 } else {
37 result += (k - j + 1) * (k - j) / 2;
38 result %= MOD;
39 break;
40 }
41 }
42 }
43 }
44 return result;
45 }
46};
47
48int main() {
49 Solution solution;
50 vector<int> arr = {1,1,2,2,3,3,4,4,5,5};
51 int target = 8;
52 int result = solution.threeSumMulti(arr, target);
53 cout << result << endl; // Output: 20
54 return 0;
55}The C++ solution is similar to the C one but uses STL features such as std::sort for sorting and std::vector for dynamic arrays. It sorts the input and iterates over it while checking for pairs using two pointers. The pointer positions are adjusted based on whether their sum is less, more, or equal to the required remaining sum, counting the combinations appropriately.
In this approach, we utilize hashmaps/dictionaries to store the frequency of each number in the array. Then, iterate through unique pairs of numbers to check if the pair with any other number sums up to the target value. This approach makes use of combinatorial calculations without explicitly sorting the array.
Time Complexity: O(n^2), which comes from iterating over pairs and can be considered effectively O(n) for small arrays using fixed range.
Space Complexity: O(1), as the frequency dictionary can be considered a fixed size due to constraints.
1class Solution:
2 def threeSumMulti
This Python solution makes use of combinations evaluated through mathematical formulas counting indirect combinations by their frequency. It differentiates cases where numbers are equal or different and handles all scenarios precisely.