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.
1function threeSum(nums) {
2 nums.sort((a, b) => a - b);
3 const res = [];
4 for (let i = 0; i < nums.length; i++) {
5 if (i > 0 && nums[i] === nums[i - 1]) continue;
6 let left = i + 1, right = nums.length - 1;
7 while (left < right) {
8 const sum = nums[i] + nums[left] + nums[right];
9 if (sum === 0) {
10 res.push([nums[i], nums[left], nums[right]]);
11 while (left < right && nums[left] === nums[left + 1]) left++;
12 while (left < right && nums[right] === nums[right - 1]) right--;
13 left++;
14 right--;
15 } else if (sum < 0) {
16 left++;
17 } else {
18 right--;
19 }
20 }
21 }
22 return res;
23}In JavaScript, the algorithm sorts the array and then applies two pointers within a loop to identify unique triplet combinations summing to zero, utilizing checks to exclude duplicates adjacent to processed elements.
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.