JavaScript
class Solution {
// Solution using sorting and two pointers
threeSum(nums) {
const result = [];
nums.sort((a, b) => a - b);
for (let i = 0; i < nums.length - 2; i++) {
// Skip duplicates for the first number
if (i > 0 && nums[i] === nums[i - 1]) continue;
let left = i + 1;
let right = nums.length - 1;
while (left < right) {
const sum = nums[i] + nums[left] + nums[right];
if (sum === 0) {
result.push([nums[i], nums[left], nums[right]]);
// Skip duplicates
while (left < right && nums[left] === nums[left + 1]) left++;
while (left < right && nums[right] === nums[right - 1]) right--;
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
// Time complexity: O(n²)
// Space complexity: O(1) (not counting output space)
// Solution using Set
threeSumSet(nums) {
const res = new Set();
nums.sort((a, b) => a - b);
for (let i = 0; i < nums.length; i++) {
let seen = new Set();
for (let j = i + 1; j < nums.length; j++) {
const complement = -(nums[i] + nums[j]);
if (seen.has(complement)) {
res.add(JSON.stringify([nums[i], complement, nums[j]].sort((a, b) => a - b)));
}
seen.add(nums[j]);
}
}
return Array.from(res).map(x => JSON.parse(x));
}
// Time complexity: O(n²)
// Space complexity: O(n)
}
Java
class Solution {
// Solution using sorting and two pointers
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
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 sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
result.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--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
// Solution using HashSet
public List<List<Integer>> threeSumSet(int[] nums) {
Set<List<Integer>> result = new HashSet<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
Set<Integer> seen = new HashSet<>();
for (int j = i + 1; j < nums.length; j++) {
int complement = -(nums[i] + nums[j]);
if (seen.contains(complement)) {
List<Integer> triplet = Arrays.asList(nums[i], complement, nums[j]);
Collections.sort(triplet);
result.add(triplet);
}
seen.add(nums[j]);
}
}
return new ArrayList<>(result);
}
}
Python
class Solution:
# Solution using sorting and two pointers
def threeSum(self, nums: List[int]) -> List[List[int]]:
result = []
nums.sort()
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue
left, right = i + 1, len(nums) - 1
while left < right:
curr_sum = nums[i] + nums[left] + nums[right]
if curr_sum == 0:
result.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
elif curr_sum < 0:
left += 1
else:
right -= 1
return result
# Solution using set
def threeSumSet(self, nums: List[int]) -> List[List[int]]:
result = set()
nums.sort()
for i in range(len(nums) - 2):
seen = set()
for j in range(i + 1, len(nums)):
complement = -(nums[i] + nums[j])
if complement in seen:
result.add(tuple(sorted([nums[i], complement, nums[j]])))
seen.add(nums[j])
return [list(x) for x in result]