15.md

题目地址

https://leetcode-cn.com/problems/3sum/

解答

def threeSum(nums, target=0):
    """ 三数之和(target为0时双指针非最优解) """
    nums.sort()
    res = []
    for i in range(len(nums)):
        if i == 0 or nums[i] > nums[i - 1]:
            l = i + 1
            r = len(nums) - 1
            while l < r:
                s = nums[i] + nums[l] + nums[r]
                if s == target:
                    res.append([nums[i], nums[l], nums[r]])
                    l += 1
                    r -= 1
                    while l < r and nums[l] == nums[l - 1]:
                        l += 1
                    while r > l and nums[r] == nums[r + 1]:
                        r -= 1
                elif s > target:
                    r -= 1
                else:
                    l += 1
    return res

解答2

def threeSum(nums):
    """ 三数之和为0 """
    dic = {}
    for num in nums:
        if num not in dic:
            dic[num] = 0
        dic[num] += 1
    if 0 in dic and dic[0] > 2:
        res = [[0, 0, 0]]
    else:
        res = []
    positive_num = (p for p in dic if p > 0)
    negative_num = (n for n in dic if n < 0)
    for p in positive_num:
        for n in negative_num:
            inverse = -(p + n)
            if inverse in dic:
                if inverse == p and dic[p] > 1:
                    res.append([p, n, inverse])
                elif inverse == n and dic[n] > 1:
                    res.append([p, n, inverse])
                elif inverse > p or inverse < n or inverse == 0:
                    res.append([p, n, inverse])
    return res