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 <stdio.h>
2#include <stdlib.h>
3
4#define MOD 1000000007
5
6int compare(const void *a, const void *b) {
7 return (*(int *)a - *(int *)b);
8}
9
10int threeSumMulti(int* arr, int arrSize, int target) {
11 qsort(arr, arrSize, sizeof(int), compare);
12
13 long long result = 0;
14 for (int i = 0; i < arrSize; i++) {
15 int j = i + 1, k = arrSize - 1;
16 int remainder = target - arr[i];
17 while (j < k) {
18 if (arr[j] + arr[k] < remainder) {
19 j++;
20 } else if (arr[j] + arr[k] > remainder) {
21 k--;
22 } else if (arr[j] != arr[k]) {
23 int leftCount = 1, rightCount = 1;
24 while (j + 1 < k && arr[j] == arr[j + 1]) {
25 leftCount++;
26 j++;
27 }
28 while (k - 1 > j && arr[k] == arr[k - 1]) {
29 rightCount++;
30 k--;
31 }
32 result += (leftCount * rightCount) % MOD;
33 result %= MOD;
34 j++;
35 k--;
36 } else {
37 // arr[j] == arr[k]
38 result += ((k - j + 1) * (k - j) / 2) % MOD;
39 result %= MOD;
40 break;
41 }
42 }
43 }
44 return (int) result;
45}
46
47int main() {
48 int arr[] = {1,1,2,2,3,3,4,4,5,5};
49 int target = 8;
50 int result = threeSumMulti(arr, 10, target);
51 printf("%d\n", result); // Output: 20
52 return 0;
53}The C solution begins by sorting the input array using Quick Sort. It then iterates over the array and for each element, uses the two-pointer technique to locate pairs that along with the current element add up to the target. Counts of repeated numbers are handled carefully to ensure all combinations are considered.
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.