This approach involves first sorting the array. With the array sorted, you can iterate through the array with a fixed element and use two pointers to find pairs that sum to the negative of the fixed element, effectively finding triplets. This takes advantage of the sorted order to efficiently eliminate duplicates and explore potential solutions.
Time Complexity: O(n^2), where n is the length of the array. Sorting the array takes O(n log n) and each element is processed with O(n) operations using the two-pointer technique.
Space Complexity: O(n) due to the space used for the output list and auxiliary storage for pointers.
1#include <stdio.h>
2#include <stdlib.h>
3
4int cmp(const void *a, const void *b) {
5 return *(int*)a - *(int*)b;
6}
7
8int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
9 qsort(nums, numsSize, sizeof(int), cmp);
10 int **res = malloc(numsSize * sizeof(int*));
11 *returnSize = 0;
12 *returnColumnSizes = malloc(numsSize * sizeof(int));
13
14 for (int i = 0; i < numsSize - 2; i++) {
15 if (i > 0 && nums[i] == nums[i - 1]) continue;
16 int left = i + 1, right = numsSize - 1;
17 while (left < right) {
18 int sum = nums[i] + nums[left] + nums[right];
19 if (sum < 0) left++;
20 else if (sum > 0) right--;
21 else {
22 res[*returnSize] = malloc(3 * sizeof(int));
23 res[*returnSize][0] = nums[i];
24 res[*returnSize][1] = nums[left];
25 res[*returnSize][2] = nums[right];
26 (*returnColumnSizes)[*returnSize] = 3;
27 (*returnSize)++;
28 while (left < right && nums[left] == nums[left + 1]) left++;
29 while (left < right && nums[right] == nums[right - 1]) right--;
30 left++;
31 right--;
32 }
33 }
34 }
35 return res;
36}The solution first sorts the input array. It iterates through each element, while using two pointers to find two numbers that form a zero-sum triplet with the selected number. The two-pointer strategy makes it efficient to skip duplicates and quickly adjust to find valid pairs.
This approach employs a hash set to track previously seen elements during pointer adjustment. This helps guide pointer movement and ensures uniqueness without repetitive triplet computation by leveraging stored hash values.
Time Complexity: O(n^2). Each combination is checked in the sorted array, similar to the two-pointer method.
Space Complexity: O(n) for auxiliary arrays supporting hash checks.
1#include <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4
5int cmp(const void *a, const void *b) {
6 return *(int*)a - *(int*)b;
7}
8
9bool* seen = NULL;
10
11void reset_seen(int n) {
12 for (int i = 0; i < n; i++) seen[i] = false;
13}
14
15int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
16 qsort(nums, numsSize, sizeof(int), cmp);
17 int** res = malloc(numsSize * sizeof(int*));
18 *returnSize = 0;
19 *returnColumnSizes = malloc(numsSize * sizeof(int));
20 seen = calloc(numsSize, sizeof(bool));
21
22 for (int i = 0; i < numsSize - 2; i++) {
23 if (i > 0 && nums[i] == nums[i - 1]) continue;
24 int left = i + 1, right = numsSize - 1;
25 reset_seen(numsSize);
26 while (left < right) {
27 int sum = nums[i] + nums[left] + nums[right];
28 if (sum == 0) {
29 if (!seen[left]) {
30 res[*returnSize] = malloc(3 * sizeof(int));
31 res[*returnSize][0] = nums[i];
32 res[*returnSize][1] = nums[left];
33 res[*returnSize][2] = nums[right];
34 (*returnColumnSizes)[*returnSize] = 3;
35 (*returnSize)++;
36 seen[left] = true;
37 }
38 left++;
39 right--;
40 } else if (sum < 0) {
41 left++;
42 } else {
43 right--;
44 }
45 }
46 }
47 free(seen);
48 return res;
49}This C implementation incorporates a hash-like boolean array (seen) to track output triplets, ensuring each triplet is considered uniquely despite sorting-based overlap.