# 15. 3Sum

## 09 Jan 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`

https://blog.csdn.net/qq_37821701/article/details/111772660

class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
pairs = collections.defaultdict(list)
n = len(nums)
ans = set()

for i in range(n):
for j in range(i+1,n):
pairs[nums[i]+nums[j]].append((i,j))

for i in range(n):
if (0-nums[i]) not in pairs:
continue
for pair in pairs[0-nums[i]]:
if i != pair[0] and i!=pair[1]:

return ans;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
res = []
nums.sort()
n = len(nums)
for i in range(n):
# we will search three numbers start from index i. So if nums[i]>0 and the nums is sorted, not valid triplets will appear
if nums[i]>0:
break
# only use the first accounted number to avoid duplicates
if i==0 or nums[i-1]!=nums[i]:
# use two pointer to search for pairs for nums[i]
lo = i+1
hi = n-1
while lo<hi:
_sum = nums[i] + nums[lo] +nums[hi]
if _sum < 0:
lo += 1
elif _sum > 0:
hi -= 1
else:
res.append((nums[i],nums[lo],nums[hi]))
lo += 1
hi -= 1
# again, we need to avoid duplicates. But we only need to do it for lo or hi, because once one of them is changed, the other will change to
while lo<hi and nums[lo]==nums[lo-1]:
lo += 1
return res
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

class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
res = []
nums.sort()
n = len(nums)
for i in range(n):
# we will search three numbers start from index i. So if nums[i]>0 and the nums is sorted, not valid triplets will appear
if nums[i]>0:
break
# only use the first accounted number to avoid duplicates
if i==0 or nums[i-1]!=nums[i]:
# use hash table to search for pairs for nums[i]
# seen use to keep the second element that has appeared, so the we can search for the pairs in O(n) rather than O(n^2)
seen = {}
j = i+1
while j<n:
remain = -nums[i]-nums[j]
if remain in seen:
res.append((nums[i],nums[j],remain))
# again, we need to avoid duplicates,here we must compare nums[j+1] and nums[j] rather than nums[j-1] and nums[j] because j is initially set to i+1. we don’t move j when nums[j] happens to be equal to nums[i]
while j+1<n and nums[j+1]==nums[j]:
j += 1
seen[nums[j]] = True;
j += 1

return res

``````class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
results = []
nums.sort()
n = len(nums)

for i in range(n):
if nums[i] > 0:
break

if i == 0 or nums[i-1] != nums[i]:
low = i+1
high = n-1
print(low)
print(high)
while low < high:
# print("********************")
# print(low)
# print(high)
# print(i)
tmp_sum = nums[low] + nums[high] + nums[i]

if tmp_sum < 0:
low += 1
elif tmp_sum > 0:
high -= 1
else:
results.append((nums[i], nums[low], nums[high]))
low += 1
high -= 1

while low < high and nums[low] == nums[low - 1]:
low += 1
print("----------------------")
return results
``````