# 15 3Sum

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`

For each `num` in the array, find two other numbers from the rest of the array whose sum is `-num`

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 `````` ``````class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: res, dups = set(), set() seen = {} for i, v1 in enumerate(nums): # dup case is already coverd by the prev iterations if v1 not in dups: dups.add(v1) for j, v2 in enumerate(nums[i+1:]): v3 = -(v1 + v2) if v3 in seen and seen[v3] == i: # seen in the same outer iteration res.add(tuple(sorted([v1, v2, v3]))) seen[v2] = i # label the outer iteration idx return res ''' Sort first ''' class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: res = [] nums.sort() for i in range(len(nums)): if nums[i] > 0: break if i == 0 or nums[i - 1] != nums[i]: self.find_two_sum(nums, i, res) return res def find_two_sum(self, nums: List[int], i: int, res: List[List[int]]): lo, hi = i + 1, len(nums) - 1 while (lo < hi): s = nums[i] + nums[lo] + nums[hi] if s < 0: lo += 1 elif s > 0: hi -= 1 else: res.append([nums[i], nums[lo], nums[hi]]) lo += 1 hi -= 1 while lo < hi and nums[lo] == nums[lo - 1]: lo += 1``````
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 `````` ``````func threeSum(nums []int) [][]int { var res [][]int sort.Ints(nums) for i := 0; i < len(nums)-2; i++ { if i > 0 && nums[i] == nums[i-1] { // case already covered by the previous iterations continue } target, left, right := -nums[i], i+1, len(nums)-1 for left < right { sum := nums[left] + nums[right] if sum == target { res = append(res, []int{nums[i], nums[left], nums[right]}) left++ right-- for left < right && nums[left] == nums[left-1] { left++ } for left < right && nums[right] == nums[right+1] { right-- } } else if sum > target { right-- } else if sum < target { left++ } } } return res }``````