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

解法1：hash table + sort triplets
这解法T了，应该是T在遍历之前储存的pair那边。不过我个人感觉这种做法比较直观

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]:
ans.add(tuple(sorted((nums[i],nums[pair[0]],nums[pair[1]]))))

return ans;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
下面两种解法参考Leetcode官方

解法2：双指针+排序
两个关键点：

排序来有效避免重复组合的出现
双指针求two sum减少时间复杂度
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
解法3：hash table + 排序
外循环和避免重复组合的方法与解法2一致，只是two sum用hash table来作

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