3Sum Problem Solution [Leetcode]

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.

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;
}