三数之和

题目

给定一个包含 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)

# Time: O(N^3), Space: O(1)
def threeSum(self, nums):
    # 爆破
    pass

2,排序+双指针,外层遍历作为a,内层用双指针寻找b c,使得a+b+c=0。Time: O(N^2), Space: O(1)
具体思路如下:

标签:数组遍历
首先对数组进行排序,排序后固定一个数 nums[i]nums[i],再使用左右指针指向 nums[i]nums[i]后面的两端,数字分别为 nums[L]nums[L] 和 nums[R]nums[R],计算三个数的和 sumsum 判断是否满足为 00,满足则添加进结果集
如果 nums[i]nums[i]大于 00,则三数之和必然无法等于 00,结束循环
如果 nums[i]nums[i] == nums[i-1]nums[i−1],则说明该数字重复,会导致结果重复,所以应该跳过
当 sumsum == 00 时,nums[L]nums[L] == nums[L+1]nums[L+1] 则会导致结果重复,应该跳过,L++L++
当 sumsum == 00 时,nums[R]nums[R] == nums[R-1]nums[R−1] 则会导致结果重复,应该跳过,R--R−−
时间复杂度:O(n^2),n为数组长度
class Solution:
    def threeSum(self, nums):
        if not nums or len(nums) < 3:
            return []
        nums.sort()  # 先排序
        ans = []

        lenth = len(nums)
        for i in range(lenth):  # 外层循环
            if nums[i] > 0:
                break
            if i > 0 and nums[i] == nums[i - 1]:  # 防止相邻i相同出现重复值,不要比较i和i+1,因为当前i和i+1也许会和其他一个数组成一个元祖
                continue
            L = i + 1
            R = lenth - 1
            while L < R:
                sum = nums[i] + nums[L] + nums[R]
                if sum < 0:
                    L += 1
                elif sum > 0:
                    R -= 1
                elif sum == 0:
                    ans.append([nums[i], nums[L], nums[R]])  # 找到
                    while L < R and nums[L] == nums[L + 1]:  # 防止相邻L相同出现重复值
                        L += 1
                    while L < R and nums[R] == nums[R - 1]:  # 防止相邻R相同出现重复值
                        R -= 1
                    L += 1  # 继续走
                    R -= 1
        return ans

3,遍历外面两层a b,判断c在不在内层,内层用哈希表查找O(1)。Time: O(N^2), Space: O(N)

def threeSum(self, nums):
    if len(nums) < 3:
        return []
    nums.sort()
    ans = set()

    for i, a in enumerate(nums[:-2]):
        if a > 0:
            break
        if i > 0 and a == nums[i-1]:
            continue
        hash_dict = {}
        for b in nums[i+1:]:
            if b not in hash_dict:  # 把 c 加入哈希表
                hash_dict[-(a+b)] = 1
            else:
                ans.add((a, -(a+b), b))
    return map(list, ans)
12-22 12:36