def threeSum(nums):
nums.sort()
triplets = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue
left = i + 1
right = len(nums) - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total < 0:
left += 1
elif total > 0:
right -= 1
else:
triplets.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
return triplets
nums = [-1, 0, 1, 2, -1, -4]
print(threeSum(nums))
Explanation:
The "3Sum" problem asks to find all unique triplets in the array that sum up to zero.
The Python, Java, and C++ solutions follow a similar approach:
Sort the array in ascending order.
Iterate over the array and fix the first element of the potential triplet (nums[i]).
Use two pointers, left and right, to find the other two elements that sum up to the negative of nums[i].
Skip duplicates by checking if the current number is the same as the previous one.
If the sum is less than zero, increment the left pointer.
If the sum is greater than zero, decrement the right pointer.
If the sum is equal to zero, add the triplet to the result list and move both left and right pointers while skipping duplicates.
Repeat the above steps for all elements in the array.
The time complexity of the solution is O(n^2), where n is the number of elements in the array.
I hope this explanation helps! Let me know if you have any further questions.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
public List> threeSum(int[] nums) {
Arrays.sort(nums);
List> triplets = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
int total = nums[i] + nums[left] + nums[right];
if (total < 0) {
left++;
} else if (total > 0) {
right--;
} else {
triplets.add(Arrays.asList(nums[i], nums[left], nums[right]));
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
left++;
right--;
}
}
}
return triplets;
}
public static void main(String[] args) {
int[] nums = {-1, 0, 1, 2, -1, -4};
Solution solution = new Solution();
System.out.println(solution.threeSum(nums));
}
}
Explanation:
The "3Sum" problem asks to find all unique triplets in the array that sum up to zero.
The Python, Java, and C++ solutions follow a similar approach:
Sort the array in ascending order.
Iterate over the array and fix the first element of the potential triplet (nums[i]).
Use two pointers, left and right, to find the other two elements that sum up to the negative of nums[i].
Skip duplicates by checking if the current number is the same as the previous one.
If the sum is less than zero, increment the left pointer.
If the sum is greater than zero, decrement the right pointer.
If the sum is equal to zero, add the triplet to the result list and move both left and right pointers while skipping duplicates.
Repeat the above steps for all elements in the array.
The time complexity of the solution is O(n^2), where n is the number of elements in the array.
I hope this explanation helps! Let me know if you have any further questions.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector> threeSum(vector& nums) {
sort(nums.begin(), nums.end());
vector> triplets;
for (int i = 0; i < nums.size() - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.size() - 1;
while (left < right) {
int total = nums[i] + nums[left] + nums[right];
if (total < 0) {
left++;
} else if (total > 0) {
right--;
} else {
triplets.push_back({nums[i], nums[left], nums[right]});
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
left++;
right--;
}
}
}
return triplets;
}
int main() {
vector nums = {-1, 0, 1, 2, -1, -4};
vector> result = threeSum(nums);
for (const auto& triplet : result) {
for (const int& num : triplet) {
cout << num << " ";
}
cout << endl;
}
return 0;
}
Explanation:
The "3Sum" problem asks to find all unique triplets in the array that sum up to zero.
The Python, Java, and C++ solutions follow a similar approach:
Sort the array in ascending order.
Iterate over the array and fix the first element of the potential triplet (nums[i]).
Use two pointers, left and right, to find the other two elements that sum up to the negative of nums[i].
Skip duplicates by checking if the current number is the same as the previous one.
If the sum is less than zero, increment the left pointer.
If the sum is greater than zero, decrement the right pointer.
If the sum is equal to zero, add the triplet to the result list and move both left and right pointers while skipping duplicates.
Repeat the above steps for all elements in the array.
The time complexity of the solution is O(n^2), where n is the number of elements in the array.
I hope this explanation helps! Let me know if you have any further questions.