<p>Given an integer array nums, return all the triplets <code>[nums[i], nums[j], nums[k]]</code> such that <code>i != j</code>, <code>i != k</code>, and <code>j != k</code>, and <code>nums[i] + nums[j] + nums[k] == 0</code>.</p>

<p>Notice that the solution set must not contain duplicate triplets.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [-1,0,1,2,-1,-4]
<strong>Output:</strong> [[-1,-1,2],[-1,0,1]]
<strong>Explanation:</strong> 
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.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [0,1,1]
<strong>Output:</strong> []
<strong>Explanation:</strong> The only possible triplet does not sum up to 0.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [0,0,0]
<strong>Output:</strong> [[0,0,0]]
<strong>Explanation:</strong> The only possible triplet sums up to 0.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>3 &lt;= nums.length &lt;= 3000</code></li>
	<li><code>-10<sup>5</sup> &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        # sort the arr
        # iterate the nums
            # target = cur num (i.e. find the sum for the rest = cur num)
            # using 2 pointers (left from cur index, right from end)
            # if num[l] + num[r] == -target , append ans,  > target r-- , M target l++
        nums.sort()  # O(NlogN)
        ans = set()  # Space: O(N)
        for i, n in enumerate(nums):  #O(N)
            l = i+1
            r = len(nums) - 1
            target = -n
            while l < r: #O(N)
                two_sum = nums[l] + nums[r]
                if two_sum == target:
                    ans.add((n, nums[l], nums[r]))
                    l += 1
                    r -= 1

                elif two_sum > target:
                    r -= 1
                else:
                    l += 1

        res = [] # Space: O(N)
        for t in ans:  # O(N)
            res.append(list(t))

        # Compute: O(NlogN + O(N^2) + O(N))
        # Space: O(N) + O(N)
        return res
21600