3Sum Problem Solution [Leetcode]

3Sum Problem: Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != ji != 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;
}


If You Like This Page Then Make Sure To Follow Us on Facebook, G News and Subscribe Our YouTube Channel. We will provide you updates daily.
Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment