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.
1def threeSum(nums):
2 nums.sort()
3 res = []
4 for i in range(len(nums)):
5 if i > 0 and nums[i] == nums[i-1]:
6 continue
7 left, right = i + 1, len(nums) - 1
8 while left < right:
9 sum_val = nums[i] + nums[left] + nums[right]
10 if sum_val == 0:
11 res.append([nums[i], nums[left], nums[right]])
12 while left < right and nums[left] == nums[left + 1]:
13 left += 1
14 while left < right and nums[right] == nums[right - 1]:
15 right -= 1
16 left += 1
17 right -= 1
18 elif sum_val < 0:
19 left += 1
20 else:
21 right -= 1
22 return resIn Python, the solution uses list sorting followed by a loop to process each potential triplet with two pointers. This design retains unique results by checking adjacent duplicates before advancing pointers.
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.