题目
解法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:continuefor 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;
下面两种解法参考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 appearif nums[i]>0:break# only use the first accounted number to avoid duplicatesif i==0 or nums[i-1]!=nums[i]:# use two pointer to search for pairs for nums[i]lo = i+1hi = n-1while lo<hi:_sum = nums[i] + nums[lo] +nums[hi]if _sum < 0:lo += 1elif _sum > 0:hi -= 1else:res.append((nums[i],nums[lo],nums[hi]))lo += 1hi -= 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 towhile lo<hi and nums[lo]==nums[lo-1]:lo += 1return res
解法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 appearif nums[i]>0:break# only use the first accounted number to avoid duplicatesif 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+1while 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 += 1seen[nums[j]] = True;j += 1return res