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.
1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4
5public class ThreeSum {
6 public List<List<Integer>> threeSum(int[] nums) {
7 Arrays.sort(nums);
8 List<List<Integer>> res = new ArrayList<>();
9 for (int i = 0; i < nums.length; i++) {
10 if (i > 0 && nums[i] == nums[i-1]) continue;
11 int left = i + 1, right = nums.length - 1;
12 while (left < right) {
13 int sum = nums[i] + nums[left] + nums[right];
14 if (sum == 0) {
15 res.add(Arrays.asList(nums[i], nums[left], nums[right]));
16 while (left < right && nums[left] == nums[left+1]) left++;
17 while (left < right && nums[right] == nums[right-1]) right--;
18 left++;
19 right--;
20 } else if (sum < 0) {
21 left++;
22 } else {
23 right--;
24 }
25 }
26 }
27 return res;
28 }
29}This Java solution involves sorting the array, then iterating through it with a fixed element while using two pointers for identifying potential pairs. The structure is efficient in checking for duplicates through comparison and pointer adjustments.
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.