3Sum Leetcode Solution
In this tutorial, we are going to solve the 3Sum problem of leetcode in python.
Task:
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.
Example 2:
Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.
Example 3:
Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.
Constraints:
3 <= nums.length <= 3000-105 <= nums[i] <= 105
Solution:
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
if nums is None or len(nums) == 1:
return None
s = set()
nums.sort()
for i in range(len(nums)-2):
if i!=0 and nums[i] == nums[i-1]:
continue
l, r = i+1, len(nums)-1
while l < r:
if nums[i]+nums[l]+nums[r] == 0:
s.add((nums[i],nums[l],nums[r]))
l+=1
r-=1
elif nums[i]+nums[l]+nums[r] > 0:
r-=1
else:
l+=1
return list(s)
Steps:
step1: first, we added the base case i.e if nums in None or its length is 1.
step2: then, we declare a set and sort the nums array with sort() function.
step3: we are using two pointer technique in this problem.
step4: we loop in the range of length of array - 2.
step5: then we declare two pointers and applied the while loop to check the given problem condition and adding it to the set and return it at the end of the function.
