题目描述
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[[-1, 0, 1], [-1, -1, 2]]
解题思路
1.暴力法
最简单直观的解法是暴力枚举，时间复杂度 O(n^3)，空间复杂度 O(1)。枚举了所有的三元组，并使用set去重。最后时间复杂度降为 O(n^2logn)。
时间复杂度$O(n^3)$，空间复杂度$O(1)$
2.双指针法
在暴力法中，很多枚举的三元组都是无效的，因此需要换一种方式减少无效的枚举。
首先，将数组从小到大排序，固定一个元素，然后使用双指针法去寻找另外两个元素，使用双指针可能找不到合法的两个元素，因此我们需要在固定一个元素之后需要先判断这个元素是否有重复出现的情况。
另外，因为要求三元组不重复，因此在找到一组合法的三元组之后，需要移动指针去寻找下一组三元组，即避免重复。
时间复杂度$O(n^2)$，空间复杂度$O(1)$
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
ans = []
nums.sort()
for i in range(n):
if i > 0 and nums[i] == nums[i - 1]: # 跳过重复的元素
continue
l, r = i + 1, n - 1 # l 为左指针，r 为右指针
while l < r:
s = nums[i] + nums[l] + nums[r]
if s < 0:
l += 1
elif s > 0:
r -= 1
else:
ans.append([nums[i], nums[l], nums[r]])
while l < r and nums[l] == nums[l+1]: # 跳过重复的元素
l += 1
while l < r and nums[r] == nums[r-1]: # 跳过重复的元素
r -= 1
l += 1
r -= 1
return ans
3.哈希表法
另外一种巧妙的解法是使用哈希表，时间复杂度为 O(n^2)，空间复杂度为 O(n)。
这个题中，我们可以将第三个元素 c 作为枚举情况，那么只需要去找出数组中存在 b + c = -a 的 a 和 b 即可。
我们可以将数组中的元素放入哈希表中，其中 key 值即为元素值，value 值为下标。在确定c的情况下，通过哈希表快速的找到一个元素 equals -a - b 即可。因此时间复杂度为O(n).
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
if n < 3:
return []
nums.sort()
ans = set()
for i in range(n):
if nums[i] > 0:
break
if i > 0 and nums[i] == nums[i - 1]:
continue
left, right = i + 1, n - 1
while left < right:
if nums[i] + nums[left] + nums[right] == 0:
ans.add((nums[i], nums[left], nums[right]))
left += 1
right -= 1
elif nums[i] + nums[left] + nums[right] > 0:
right -= 1
else:
left += 1
return list(ans)
总结
以上就是本题的三种解法，暴力法、双指针法和哈希表法。其中哈希表法是相对较为高效的一种算法，空间复杂度可以在 O(n) 的常数级别内算出。
在实际的面试过程中，根据时间和空间方面的需求不同，也会选择不同的算法。因此为了掌握更多的算法知识，我们需要在日常的练习过程中，多去了解和尝试不同的算法。
壹涵网络我们是一家专注于网站建设、企业营销、网站关键词排名、AI内容生成、新媒体营销和短视频营销等业务的公司。我们拥有一支优秀的团队，专门致力于为客户提供优质的服务。
我们致力于为客户提供一站式的互联网营销服务，帮助客户在激烈的市场竞争中获得更大的优势和发展机会！
发表评论 取消回复