3Sum Problem: 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 1:
Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]] Explanation: nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0. nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0. nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0. The distinct triplets are [-1,0,1] and [-1,-1,2]. Notice that the order of the output and the order of the triplets does not matter.
Table of Contents
3Sum Problem Solution
Problem Solution In Python
class Solution:
def threeSum(self, array: List[int]) -> List[List[int]]:
if len(array) < 3:
return []
if (all(num == 0 for num in array)):
return [[0, 0, 0]]
size = len(array)
found = {}
array = sorted(array)
for index, value in enumerate(array):
left = index + 1
right = size - 1
while left < right:
total = value + array[left] + array[right]
if total == 0:
current = (value, array[left], array[right])
if current not in found:
found[current] = True
right = right - 1
elif total < 0:
left = left + 1
else:
right = right - 1
return list(found.keys())
Problem Solution In Java
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Map<Integer, Integer> map = getMapWithPos(nums);
Set<List<Integer>> items = new HashSet<>();
Set<Integer> hs1 = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
if (!hs1.add(nums[i]))
continue;
Set<Integer> hs2 = new HashSet<>();
for (int k = i + 1; k < nums.length; k++) {
if (!hs2.add(nums[k]))
continue;
int n3 = -nums[i] - nums[k];
Integer pos = map.get(n3);
if (pos != null && pos > k) {
List<Integer> list = new ArrayList<>(3);
list.add(nums[i]);
list.add(nums[k]);
list.add(nums[pos]);
Collections.sort(list);
items.add(list);
}
}
}
return new ArrayList<>(items);
}
private Map<Integer, Integer> getMapWithPos(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = nums.length - 1; i >= 0; i--) {
if (!map.containsKey(nums[i]))
map.put(nums[i], i);
}
return map;
}
}
Problem Solution In C++
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
int i,low,high;
if(nums.size()<3)
return result;
sort(nums.begin(),nums.end());
for(i=0;i<nums.size()-2;i++)
{
low=i+1;high=nums.size()-1;
while(low<high)
{
if(i!=0 && nums[i]==nums[i-1])
{
break;
}
else if((nums[low]+nums[high])==-nums[i])
{
vector<int> triplet;
triplet.push_back(nums[low]);
triplet.push_back(nums[high]);
triplet.push_back(nums[i]);
result.push_back(triplet);
while(low<high && nums[low]==nums[low+1])
low++;
while(low<high && nums[high]==nums[high-1])
high--;
low++;high--;
}
else if((nums[low]+nums[high])>-nums[i])
{
high--;
}
else if((nums[low]+nums[high])<-nums[i])
{
low++;
}
}
}
return result;
}
};
Problem Solution In C
static int compare( const void a,const void b )
{
return ( (int) a -(int) b );
}
int threeSum (int nums, int numsSize, int returnSize) {
if (numsSize < 3) return NULL;
qsort (nums, numsSize, sizeof(int), compare);
int p = NULL;
int count = 0;
p=(int) malloc( 50000 sizeof (int) );
for( int i = 0; i < numsSize - 2; )
{
int temp1 = -nums[i];
int low = i+1;
int high = numsSize-1;
while( low < high )
{
int temp2 = nums[low] + nums[high];
if ( temp1 > temp2 ) low++;
else if ( temp1 < temp2 ) high--;
else
{
p[count] = (int) malloc( 3 sizeof(int) );
p[count][0] = nums[i];
p[count][1] = nums[low];
p[count][2] = nums[high];
count++;
while( low<high && nums[low] == nums[low+1] )
low++;
while( low < high && nums[high] == nums[high-1] )
high--;
low++;
high--;
}
}
i++;
while( nums[i] == nums[i-1] )
i++;
}
returnSize = count;
return p;
}