## Problem Description

The problem 3Sum is 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:

```
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
```

## Solution

To solve the problem, we follow the steps below:

We sort the array using

`nums.sort()`

.We iterate over each element in the array using a

`for`

loop.Inside the loop, we check if the current element is a positive integer or not. If it is, we break out of the loop.

If the current element is not a positive integer, we check if it is a duplicate of the previous element. If it is, we skip it using the

`continue`

statement. If it is not, we initialize two variables`l`

and`r`

.`l`

will point to the next element after the current element, and`r`

will point to the last element in the array.We then use a

`while`

loop which will continue until`l`

is less than`r`

. Inside the`while`

loop, we calculate the sum of the current element,`lth`

element, and`rth`

element. If the sum is greater than 0, we decrement`r`

using`r -= 1`

. If it is less than 0, we increment`l`

using`l += 1`

. If it is equal to 0, we append the triplet to the result and increment`l`

and decrement`r`

using`l += 1`

and`r -= 1`

. We then check if the next element after`l`

is a duplicate of the current element. If it is, we skip it using the`while`

loop.Finally, we return the result using

`return res`

.

```
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
res = []
nums.sort()
for i, a in enumerate(nums):
# Skip positive integers
if a > 0:
break
if i > 0 and a == nums[i - 1]:
continue
l, r = i + 1, len(nums) - 1
while l < r:
threeSum = a + nums[l] + nums[r]
if threeSum > 0:
r -= 1
elif threeSum < 0:
l += 1
else:
res.append([a, nums[l], nums[r]])
l += 1
r -= 1
while nums[l] == nums[l - 1] and l < r:
l += 1
return res
```

## Complexity Analysis

The time complexity of this algorithm is `O(n^2)`

. This is because we are using nested loops to iterate over the array. The space complexity of this algorithm is `O(1)`

, since we are not using any extra space.

## Conclusion

In this blog post, we have solved the LeetCode problem "3Sum" using Python. We have explained the solution step-by-step and provided a complexity analysis. Happy Coding!😎