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.
1using System;
2using System.Collections.Generic;
3
4public class ThreeSumSolution {
5 public IList<IList<int>> ThreeSum(int[] nums) {
6 Array.Sort(nums);
7 IList<IList<int>> res = new List<IList<int>>();
8 for (int i = 0; i < nums.Length; i++) {
9 if (i > 0 && nums[i] == nums[i-1]) continue;
10 int left = i + 1, right = nums.Length - 1;
11 while (left < right) {
12 int sum = nums[i] + nums[left] + nums[right];
13 if (sum == 0) {
14 res.Add(new List<int>(){nums[i], nums[left], nums[right]});
15 while (left < right && nums[left] == nums[left+1]) left++;
16 while (left < right && nums[right] == nums[right-1]) right--;
17 left++;
18 right--;
19 } else if (sum < 0) {
20 left++;
21 } else {
22 right--;
23 }
24 }
25 }
26 return res;
27 }
28}C# implementation leverages array sorting and two-pointer technique within a loop to determine valid triplets, while carefully avoiding duplicate entries by advancing pointers past equivalent values.
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 <iostream>
2#include <vector>
3#include <set>
4#include <algorithm>
5using namespace std;
6
7vector<vector<int>> threeSum(vector<int>& nums) {
8 sort(nums.begin(), nums.end());
9 set<vector<int>> res;
10 for (int i = 0; i < nums.size(); i++) {
11 if (i > 0 && nums[i] == nums[i-1]) continue;
12 int left = i + 1, right = nums.size() - 1;
13 while (left < right) {
14 int sum = nums[i] + nums[left] + nums[right];
15 if (sum == 0) {
16 res.insert({nums[i], nums[left], nums[right]});
17 left++;
18 right--;
19 } else if (sum < 0) {
20 left++;
21 } else {
22 right--;
23 }
24 }
25 }
26 return vector<vector<int>>(res.begin(), res.end());
27}This implementation in C++ utilizes a set for storing unique triplets, leveraging their properties to avoid duplicate calculations post-loop completion.