LeetCode，mdash，mdash，15.，3Sum介绍

题目描述

给定一个包含 n 个整数的数组nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例：

示例 1：

输入：nums = [-1,0,1,2,-1,-4]

输出：[[-1,-1,2],[-1,0,1]]

示例 2：

输入：nums = []

输出：[]

示例 3：

输入：nums = [0]

输出：[]

解题思路

本题最先想到的暴力解法是将三个元素组合，比较其和是否为0。但是，这样的时间复杂度显然是O(n^3)，如果数据规模较大，运行时间会非常长。

因此，需要寻找更优秀的解法。观察题目，要求三元组之和为0，那么如果先将数组进行排序，可以使用双指针的方法，将时间复杂度压缩到O(n^2)。

具体思路如下：

首先，对数组进行排序，排序后可以通过双指针的方式分别从序列的两端开始逼近，如果三个元素之和大于0，就将右侧指针向左移动，如果三个元素之和小于0，就将左侧指针向右移动，如果等于0，就将三个元素加入到答案列表中。还需要注意的是，避免出现重复的三元组，因此在添加元素之前比较一下前一个元素是否与当前元素相等，如果相等就忽略掉。

下面是具体的代码实现。

解法代码

Python3

class Solution:

def threeSum(self, nums: List[int]) -> List[List[int]]:

n = len(nums)

if n < 3:

return []

nums.sort()

ans = []

for i in range(n - 2):

if nums[i] > 0: # 由于已经排好序了，如果当前元素大于0，则后面不可能产生三个数的和为0

break

if i > 0 and nums[i] == nums[i-1]: # 避免重复

continue

left, right = i + 1, n - 1

while left < right:

s = nums[i] + nums[left] + nums[right]

if s == 0:

ans.append([nums[i], nums[left], nums[right]])

while left < right and nums[left] == nums[left+1]: # 避免重复

left += 1

while left < right and nums[right] == nums[right-1]: # 避免重复

right -= 1

left += 1

right -= 1

elif s < 0:

left += 1

else: # s > 0

right -= 1

return ans

时间复杂度分析

对数组进行排序所需要的时间复杂度为O(nlogn)，双指针的时间复杂度为O(n)。因此，总的时间复杂度为O(n^2)。

空间复杂度为O(1)，解法是直接对原数组进行操作，没有额外使用其他空间。 如果你喜欢我们三七知识分享网站的文章， 欢迎您分享或收藏知识分享网站文章 欢迎您到我们的网站逛逛喔！https://www.ynyuzhu.com/