Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.
Example:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Solution:
To solve this problem, we can use a combination of sorting and the two-pointer technique. Here's a step-by-step approach:
1. Sort the array: This will allow us to easily skip over duplicate numbers and use the two-pointer technique.
2. Iterate over the array: For each number `nums[i]`, we'll try to find pairs `nums[j]` and `nums[k]` such that their sum is `-nums[i]`.
3. Two-pointer technique: For each `nums[i]`, initialize two pointers: `j` starting at `i+1` and `k` starting at the end of the array. Then:
- If `nums[i] + nums[j] + nums[k]` is less than 0, move `j` to the right.
- If the sum is greater than 0, move `k` to the left.
- If the sum is 0, add the triplet to the result and move both pointers, skipping any duplicates.
Here's the C# code to implement this approach:
public IList<IList<int>> ThreeSum(int[] nums) {
Array.Sort(nums);
List<IList<int>> result = new List<IList<int>>();
for (int i = 0; i < nums.Length - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue; // Skip duplicates
int j = i + 1;
int k = nums.Length - 1;
while (j < k) {
int sum = nums[i] + nums[j] + nums[k];
if (sum == 0) {
result.Add(new List<int> { nums[i], nums[j], nums[k] });
j++;
k--;
// Skip duplicates for j and k
while (j < k && nums[j] == nums[j - 1]) j++;
while (j < k && nums[k] == nums[k + 1]) k--;
} else if (sum < 0) {
j++;
} else {
k--;
}
}
}
return result;
}
This solution efficiently finds all unique triplets in the array that sum up to zero.